Linkage for Halloween

An upper bound for Lebesgue’s universal covering problem (G+, \(\mathbb{M}\)). Philip Gibbs makes progress on the smallest area needed to cover a congruent copy of every diameter-one curve in the plane, with additional contributions from John Baez, Karine Bagdasaryan, and Greg Egan. See Baez’s blog post for more.

Spontaneous Venning (\(\mathbb{M}\)). Christian Lawson-Perfect simulates people (or maybe the kodama from Princess Mononoke) moving around to be closer to others like them, and finds that they spontaneously form Venn diagrams.

Patterns in nature (\(\mathbb{M}\), via). 12 shortlisted photographers for the Royal Society of Biology Photographer of the Year.

Kokichi Sugihara wins the Best Illusion of the Year (again) with an orthogonal polyhedron! (G+, \(\mathbb{M}\), via). Or maybe a different orthogonal polyhedron. Or maybe a third one. Or maybe it’s not actually orthogonal at all…

Theil–Sen (median slope) estimator, now a Good Article on Wikipedia (G+, \(\mathbb{M}\)). This is a method for fitting a line to a set of data points by finding the median slope of lines through pairs of points. It is robust, meaning that (unlike ordinary least squares) a constant fraction of the data can be arbitrarily corrupted without affecting the goodness of fit.

Garsia–Wachs algorithm (\(\mathbb{M}\), via). New Wikipedia article on an old algorithm for finding optimal binary search trees (in the special case where you care about the heights of the leaves but not the internal nodes) or optimal alphabetic Huffman codes.

Artist uses bare hands to sculpt soda cans into beautiful geometric shapes (G+, \(\mathbb{M}\)).

Shrinking the superpermutations (\(\mathbb{M}\)). Greg Egan suggests a formula for their length, and constructs superpermutations of length only one more than the formula. Superpermutations should not be confused with superpatterns, which contain all permutations of a given length for a different definition of containment, and are a lot shorter, but also somewhat mysterious in length.

A short open letter to Google on minimizing the damage of shutting down Google Plus, Peter Suber (G+, \(\mathbb{M}\)). I agree with this letter. I can rescue and rehost my individual posts if Google takes down Google+ altogether. But even if I do that, all my links to other people’s posts and all my comments on those posts will be lost. Far better to freeze Google+ but keep it online with all the existing post urls still live. To do otherwise would be to throw away all trust that any Google site is a safe haven for my content.

Programs that run all small programs in parallel and pick the winner (G+, \(\mathbb{M}\)). This idea gives the long-known but counterintuitive result that there is an already-known algorithm that, if P=NP, solves all solvable instances of satisfiability in polynomial time. Bill Gasarch gives a nice roundup of explanatory links in this new blog post.

Cornell ends a partnership with a Chinese university “because of concerns that its Chinese partner institution, Renmin University of China, had punished, surveilled or suppressed students who supported workers’ rights in a labor conflict” at a different university (\(\mathbb{M}\)). According to the quoted Cornell professor who headed and cut off the partnership, the suppression came from the national party, not Renmin.

Wikipedia’s Strickland affair (G+, \(\mathbb{M}\)). Strickland is a new Nobel prize winner who, before the prize, had never been put up for promotion to full professor (embarrassing her employer) and had two attempts at creating a Wikipedia article shot down (which should have, but apparently didn’t, embarrassed the people who did it). This trio of op-eds examines how everyone responded, how we can do better, or (in the third case) why the writer thinks we shouldn’t try to do better.

A few labeled graphs (with notes as vertices and intervals as edges), from the 1492 printing of Boethius’s De institutione musica (\(\mathbb{M}\)). Jeff Erickson finds yet another instance of graph theory before Euler’s invention of the subject in 1736.

Updates and errata to my book (G+, \(\mathbb{M}\)). I had been planning to do this eventually but what triggered me to do it now was the discovery of a paper by Czumaj, Sohler, and Ziegler (ESA 2000) on geometric property testing that I should have already been citing and that solved a problem I had listed as open.