Linkage

Relevant points for nearest-neighbor classification (\(\mathbb{M}\)). The 48-minute extended remix of my SOSA talk, from the New York computational geometry seminar, somehow still going strong decades after I first started attending it in the late 1980s.

The journal I recently co-founded, Computing in Geometry and Topology, has published its first paper! It’s “On the pathwidth of hyperbolic 3-manifolds” by Kristóf Huszár (\(\mathbb{M}\)). Hyperbolic 3-manifolds were known to have triangulations of treewidth linear in their hyperbolic volume — the paper improves this to pathwidth. Having small pathwidth, in turn, simplifies certain dynamic programming computations over tree decompositions of the triangulation.

Conway’s Game of Life: Mathematics and Construction (\(\mathbb{M}\)). Free online book by Nathaniel Johnston and Dave Greene detailing the engineering behind some of the most complex patterns in Life including universal computers, large variable-speed spaceships and replicators, and metacells that can emulate any other 2d cellular automaton.

Why isn’t there a replication crisis in math (\(\mathbb{M}\), via)? It’s not like there’s any shortage of papers with incorrect proofs in them; the bigger mystery is why, much of the time, the broken proofs turn out to be fixable.

A bug in the old version-2 Creative Commons licenses spawns a new breed of copyright troll (\(\mathbb{M}\), via): seed the open web with CC2-licensed stock photography and the like, wait for unsuspecting people to use it without exactly following the proper format of attribution, sue. Cory Doctorow describes being threatened for using one of these images despite attributing it correctly. See also a later followup from Doctorow.

Christian Lawson-Perfect asks for names for the glyph you use to depict holes in tori. Suggestions include donut hole, hologram, omphalos, and some made-up words. Incidentally, trying to re-create it as the image below ran into a bizarre Adobe Illustrator bug where saving an intersection of two circles in svg turned it into an ellipse; instead, I had to keep the top and bottom arcs as separate objects.

Squaring the circle, by cutting a square into fractal pieces and reassembling them into a circle (\(\mathbb{M}\)). The original paper, “Circle squaring with pieces of small boundary and low Borel complexity” by András Máthé, Jonathan A. Noel, and Oleg Pikhurko, is very technical, but the main improvement on earlier work in the same line of research is that now the pieces all have positive measure and their boundaries have dimension less than two. The pretty animation at the start of the Quanta link is a little misleading, though: the number of pieces is huge, around \(10^{200}\).

I made a project of illustrating an Erdős–Rényi–Gilbert random graph in which the giant component (or at least, a large component) is clearly visible (\(\mathbb{M}\)). Used social gravity to get the component centered and separated from everything else. Came out reasonably well, I think.

Ar5iv, a project for automatically converting most arXiv preprints (the ones with LaTeX source) into html (\(\mathbb{M}\), via). Too bad about the not-up-to-TeX-quality math formula formatting, though. They’re using mathml instead of MathJax, and it shows. For instance, when I view formulas like \(O\bigl(n^{4/3+\varepsilon}+k^{5/3}n^{2/3}\log^{O(1)}n\bigr)\) (from one of my recent papers) in Firefox, the exponents get at least two inconsistent baselines, maybe four. Fortunately, CLP has a MathJaxification bookmarklet that can make things better…

The lists of accepted papers are now up at the web sites for the 2022 Symposium on Computational Geometry and European Workshop on Computational Geometry (\(\mathbb{M}\)).

Factoring composite numbers into nearly equal factors (\(\mathbb{M}\)) turns out to be complete for \(\mathsf{NP}\) under randomized reductions, or properly \(\mathsf{NP}\)-complete if the gaps between prime numbers are small enough to allow a deterministic reduction from the subset sum problem to go through.

Perfectly packing a square by squares of nearly harmonic sidelength (\(\mathbb{M}\)). Terry Tao attacks an old question of whether inverse-integer squares pack into a single square of area \(\zeta(2)=\pi^2/6\), showing that squares of sides 1/integer\({}^{1+\varepsilon}\) do pack. A key insight: the high perimeter of not-yet-packed squares is an obstacle, but can be controlled by grouping squares into rough grids before packing. (This is why the epsilon is needed: perimeter diverges without it.)

What do you get when you combine an indigenous Australian painting aesthetic with vaguely-Kabbalistic astronomical charts and geometric diagrams (\(\mathbb{M}\))? Answer: the art of Shane Drinkwater.