Linkage from Toronto

Last time I did one of these posts I was in Montreal for the 3rd Joint SIAM/CAIMS Annual Meetings (AN) and its satellite conferences on geometric design (GD) and applied and computational discrete algorithms (ACDA). This time, I’m back in Canada for the Algorithms and Data Structures Symposium (WADS) and Canadian Conference on Computational Geometry (CCCG). Yes, only some of those acronyms make sense. Anyway:

• Terry Tao on the Trump administration’s ongoing attacks on research and the universities, this time taking hostage all funding for research at UCLA including both Tao’s personal grants and the funds for the IPAM mathematics institute there.

• Project Patti: Why can You solve diabolical puzzles on one Sudoku website but not easy puzzles on another Sudoku website? (\(\mathbb{M}\)). A new preprint by Arman Eisenkolb-Vaithyanathan investigates empirically an idea that has probably been developed independently many times (for me it was in a never-published 2005 preprint): to judge the difficulty of a Sudoku puzzle you should use a computer solver that mimics human deductive reasoning rather than backtracking (much easier as backtracking may be in a solver) and look at the complexity of the deductive rules you need to use for each puzzle. Eisenkolb-Vaithyanathan analyzes this idea across thousands of puzzles from five websites and finds good correlations with the website difficulty labels.

• Meet MIT’s origami genius: Eric Domain, WCVB Boston. Erik Demaine’s evil twin?

• MathJax 4.0 is out (\(\mathbb{M}\)). Maybe the most interesting feature is embedded html within mathematics expressions. Not a good idea to mix with user-generated content though, so it’s disabled by default.

• The journal Frontiers of CS casts a shadow on its reputation (\(\mathbb{M}\)) by publishing an (incorrect) proof of \(\mathsf{P}\ne\mathsf{NP}\) by its deputy editor-in-chief. Guest post on the Computational Complexity blog by Eric Allender, who coauthored a response with Ryan Williams. For another more detailed rebuttal to an earlier version of the same paper see arXiv:2312.02071.

• The snake-in-the-box problem: not what I expected to see on xkcd today (\(\mathbb{M}\)).

• The antihydra problem (\(\mathbb{M}\)): if you iterate \(x\mapsto\lfloor 3x/2\rfloor\) starting with 8, will you ever see twice as many odd numbers as even? “Probviously” not, but proving an answer seems very difficult, and is a necessary step towards calculating the next busy beaver number, \(BB(6)\).

• Lysenkoism here we come (\(\mathbb{M}\)): Trump puts all federal research grants under political rather than scientific control.

• AI crushed the Math Olympiad—or did it? (\(\mathbb{M}\), archived). Emily Riehl shares her reactions to recent claims of AI performance on the IMO, published in Scientific American.

• The Fermi–Dirac primes (\(\mathbb{M}\)), actually prime powers with power-of-two exponents, the factors in a unique factorization theorem where each factor can appear only once. The code for generating these in OEIS looks slow and bad, but if you have a streaming generator for the usual primes, then the Fermi–Dirac primes are easy to generate in sorted order: just merge the primes and the squares of the recursively generated Fermi–Dirac primes.

• You probably know about the five Platonic solids, convex polyhedra that are fundamental for point symmetries. But did you know there is a different set of five convex polyhedra, the parallelohedra (\(\mathbb{M}\)), that are just as fundamental for translational symmetries? Another new Good Article on Wikipedia.

• No, pulling standard dominoes out of a bag does not give the same probabilities as rolling two dice. Mark Gritter points out an error in Marcus Du Sautoy’s Around the World in Eighty Games.

• Breaking the sorting barrier for directed single-source shortest paths (\(\mathbb{M}\)), as discussed by Quanta and published at STOC 2025. The new time bound, \(O(m\log^{2/3} n)\), is faster than Dijkstra’s \(O(m+n\log n)\) for sparse enough graphs, meaning \(m=o(n\log^{1/3} n)\).

• The bilaterally symmetric shapes made from the five tetrominoes kind of look like Space Invaders, even if they are drawn sideways.

• Recognizing penny and marble graphs is hard for existential theory of the reals (\(\mathbb{M}\)), is a new preprint by Anna Lubiw and Marcus Schaefer. A penny graph is a graph that you can get by pushing a bunch of pennies together, flat on a tabletop; when two pennies touch each other, that forms an edge. They are a special case of the planar graphs (which, by the circle packing theorem, are the graphs you can get in this way from circles that are not all the same size) and the matchstick graphs (planar graphs that you can draw with no crossings and with all edges of equal lengths).

  Previously it was known that determining whether a given graph is a penny graph is \(\mathsf{NP}\)-hard, based on combinatorial structures in certain penny graphs that can be used to simulate logical circuits. But it was not obvious how to certify that a graph is a penny graph by providing only combinatorial information about it (a polynomial number of bits of information), because a realization as a penny graph involves real numbers that might plausibly require a non-polynomial number of bits to specify. The new preprint resolves this issue by proving that recognizing penny graphs and their 3d analogues is as hard as any other problem that involves specifying real numbers and then checking certain algebraic properties of them (like are certain tuples of them the coordinates of points that are a unit distance apart).