- Squircle illusion: now 3d printing can make things round and square at the same time (G+)
- The latest wonders of mathematical art from Bridges 2016 (G+)
- CCCG accepted papers (or now there's an actual schedule; G+)
- Low faculty uptake of the University of California's all-subjects open access repository (G+, many good comments)
- 20-minute nontechnical video documentary about recent hacking culture (G+)
- How can you divide a square into finitely many similar acute triangles? (G+)
- No article can be judged on the basis of the Impact Factor of the journal in which it is published (G+)
- Uniformly-spaced point sets in nature (see also Wikipedia on Delone sets; G+)
- A trickier variant of the 4 4's puzzle (G+, with spoilers in the comments)
- Researchers keeping a low online profile in the face of persistent harassment of anyone who criticizes misogyny in computer gaming (G+)

*n*real numbers (or other totally ordered values that you can compare but not treat as small integers). You want to answer queries that specify a contiguous subarray and return the sorted sequence of values within that subarray. Without any preprocessing you could query a subarray of length

*k*in time

*O*(

*k*log

*k*), by pulling out the subarray and then comparison sorting it. With preprocessing, how much better can we do?

**( Read more...Collapse )**

**( Read more...Collapse )**

**( Read more...Collapse )**

*x*,

*y*) in the plane, in sorted order by their Euclidean distance from the origin. How little space do you need?

**( Read more...Collapse )**

Here are some of my photos from the SWAT excursion to the Reykjanes peninsula, and of some of the participants. Iceland (even this small part of it) was easily as scenic as I had been led to believe.

- Why do women leave engineering? (G+)
- Still life prototiles (G+)
- Proceedings of the 32nd International Symposium on Computational Geometry, free online (G+)
- How fast is tabulation-based hashing? Not as fast as you might hope (G+)
- Three dimensional tessellation of crosses (G+)
- Animations of polynomial roots as one coefficient moves on a circle in the complex plane (G+)
- Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), also free online (G+)
- Iceland 2 Austria 1, a fun thing to experience in Iceland at SWAT (G+)
- Singular they, still the right way to do gender-neutral third-person pronouns (G+)
- Make your own miniature columnar basalt out of corn starch (G+)
- The 200-year history of infographics (G+)
- Having a child-care tenure-delay policy hurts women by giving a greater advantage to the men (G+)
- Researchers sue for the right to investigate algorithmic discrimination (G+)
- Chemical serindipity finds a new blue (G+)

**( More photos )**

**( Read more...Collapse )**

Sara tells me she likes the other shot better, though.

- Why screenshots of published journal articles make bad talk slides (G+)
- Fibonacci and non-Fibonacci spirals in sunflowers (G+)
- More on correlations in the moduli of consecutive primes (G+)
- Less state funding of universities = more corporate corruption (G+)
- My cross-the-street neighbor, caught up in a saga of a MOOC gone bad (G+)
- Lonely runner conjecture still not solved (G+)
- Europe considers changing its rules on freedom of panorama (i.e. whether that background building prevents you from publishing your photos; G+)
- 5-connected nonplanar graphs have topological
*K*_{5}minors (G+) - This year's Graph Drawing contest, plus a corrected issue with only informing insiders of the GD submission rules (G+)
- How much is available on arXiv? (G+)
- Uncountable trees with countable height and branching factor (see also discussion on G+)
- Stable marriage for equal area Voronoi-like cells (G+)
- Trailer for
*The Discrete Charm of Geometry*(G+) - Widest paths on Wikipedia (G+)

In many cases, even if you add some noise to a graph, its underlying irregularities will show through, allowing you to recognize it and its individual features. That's the main idea behind my most recent arXiv preprint, "Models and Algorithms for Graph Watermarking" (arXiv:1605.09425, with Goodrich, Lam, Mamano, Mitzenmacher, and Torres, to appear at ISC 2016).

The problem we study is one of watermarking copies of a graph (for instance a large social network) so that if you see one of your copies later you can tell which one it was, by using the graph structure rather than extra information such as vertex labels. To do so, we identify a small number of "landmark" high-degree vertices (generally, the ones with the highest degrees), use the pattern of adjacencies to landmarks to give unique identities to a larger set of (medium-degree) vertices, and flip a small set of randomly selected edges among these vertices. With high probability (when the graph to be watermarked is drawn from a suitable random family) even if an adversary tries to mask the watermark by scrambling the vertices or flipping more edges, the vertex identifications and pattern of flipped edges will be recoverable.

Because we're choosing our landmarks in a fairly naive way (by vertex degrees, or as in our implementation with ties broken by neighboring degrees), our algorithms wouldn't work for random regular graphs. But even in such cases, there are other features such as the numbers of triangles they belong to or their distance vectors that often allow some vertices to be distinguished from others. Finding out which features of this type remain robust when noise is added to the graph seems like a promising line of research.

- A parity theorem for drawings of complete graphs (G+)
- Social-sciences preprint server SSRN bought by Elsevier (G+)
- More than one way to draw an ellipse (G+)
- kleinian, a tool for visualizing Kleinian groups (G+)
- Cheese charts. Really, is it any stranger a thing to call them than pie charts? (G+)
- Rule 184, three particle systems in one (G+)
- Russian black-market dissertations (G+)
- Motoi Yamamoto's salt labyrinths (G+)
- Do you like DAGs? (G+)
- Android makes fair use of JAVA APIs (G+)
- The stretched model of the hyperbolic plane, in which most lines are modeled as half-hyperbolas (G+)
- Google maps now more of a route-planner than a usable map (G+)
- Pushing for all funded research to be free to read (G+)

Ivan Pervushin was a 19th-century Russian amateur mathematician, employed as a cleric, who factored two Fermat numbers and discovered the ninth Mersenne prime 2^{61} − 1 = 2305843009213693951. But despite these obvious reasons for fame, his Wikipedia article was in such bad shape (e.g. completely unsourced) that it was recently put up for a deletion discussion, which it survived.

**( Read more...Collapse )**

For now, you can visit http://cs.brown.edu/~pnk/#soda17 for the basic information (deadlines, submission site, and program committee).

**( Read more...Collapse )**

You may have heard of the Poincaré disk model of the hyperbolic plane, in which the whole hyperbolic plane is mapped to the interior of a Euclidean disk, with hyperbolic lines being transformed into circular arcs that make a right angle with the disk boundary. Or of the Beltrami–Klein model, which also maps the hyperbolic plane to the interior of a disk, but with a different map that keeps the lines straight, so that they correspond to the chords of a circle.

One use for these models is in information visualization, to provide a fisheye view of a drawing in the hyperbolic plane that provides "focus+context": focus on some specific feature in the drawing, and context of all the rest of the drawing, compressed into the outer parts of the disk. Another is as an aid to mathematical intuition: hyperbolic lines may be hard to visualize and understand, but chords of a circle are much more familiar, and this model shows that (in terms of the combinatorial patterns they can perform, if not their distances and angles) they are really the same thing.

But did you know that you can get an analogous fisheye view of the Euclidean plane, by another pair of models that map Euclidean lines to natural families of curves in a disk?

**( Read more...Collapse )**

- Andrew Suk solves the happy ending problem (G+)
- CCCG is in Vancouver this year; submission deadline is this Tuesday, May 17 (G+)
- Solomon W. Golomb dies (G+)
- A sculptural geometric pop-up book by Tauba Auerbach (G+)
- Apple's cloud music storage can wipe your local copies and replace them with ersatz substitutes (G+)
- Harvard penalizes members of gender-exclusive organizations (G+)
- Matching reviewers to submissions still needs some human attention (G+)
- Removed from a plane for doing mathematics (G+)
- "No, I am not pregnant": yet another example of everyday sexism in academia, mostly invisible to men (G+)
- Australian government issues report calling for copyright and patent liberalisation (G+)
- Binary search, now another Wikipedia good article (G+)
- Origami robots that can perform surgery on your digestive system after you eat them (G+)
- Here Be Robots: A Medieval Map of Mars (G+)
- New uses for blockchain: ensuring the integrity of medical experiments (G+)
- An amusing 10-minute talk about NP-completeness and its application to Sesame Street (G+)

- Book embedding on Wikipedia (G+)
- The fractal geometry of plants (G+)
- A great combination of a success story of an individual woman in tech, a debunking of some nasty misogynist myths, and a collection of helpful resource links for others on the same path (G+)
- Trailer for a documentary on the shifting technology of graphic design from hand layout to computers (G+)
- Complaints about problems with peer review turn out to be far from new (G+)
- Curve-shortening flow on Wikipedia (G+)
- The Open Access Interviews: Timothy Gowers (G+)
- CMU’s computer science dean on its poaching problem (G+)
- From tilted decks of playing cards to hyperbolic geometry (G+)
- Springer journal copyrights are compatible with arXiv preprints (G+)
- Pinwheel zoom (G+)