• A 3 state, 3 symbol Turing Machine that cannot be proven to halt (\(\mathbb{M}\), via), when starting on a blank tape, without solving a Collatz-like problem.

  • Wikipedia edit-a-thon at FOCS (\(\mathbb{M}\)), the IEEE Symposium on Foundations of Computer Science, Monday November 6, in Santa Cruz. I’m not going to the conference but I wish the attendees well. If you are attending, feel free to ping my Wikipedia talk page to bring my attention to the articles you’re working on.

  • Science is a strong-link problem (\(\mathbb{M}\), via). Adam Mastroianni argues that, in the publication and grant review infrastructure of science, it is much more important to support the best work than it is to gatekeep and filter out the bottom. And more strongly, that the sort of gatekeeping that we routinely do is counterproductive, because it stifles the best work. The via link covers another side of the same story: the idea that a certain line of research (in psychology but the same could apply in many other fields) that has been hugely successful by the usual metrics of academia, and may have been based on fraud, could be totally erased from the academic record with nobody noticing its absence.

  • Use of AI for OEIS Submissions is Forbidden! (\(\mathbb{M}\)).

  • ArXiv gets infrastructure grant, to move its data to the cloud (\(\mathbb{M}\)) It’s a bit unfortunate that the only way to get this kind of funding to keep essential infrastructure like arXiv running is to pretend to do something innovative in how it runs, rather than just “please help us pay the bills to keep it running”.

  • According to Yahoo News, Google secretly changed their ad-auction algorithm (\(\mathbb{M}\), via) from a standard second-price auction to one in which the winner was charged an inflated price, closer to the first-price bid. Doing this would have the appearance of bringing in more money for each auction because it charges advertisers more while still staying under the price they’re willing to pay. But it has big downsides, once found out: it causes participants to be unwilling to bid their true price, and could cause significant fluctuation of bids well below their “true” values that leads to bringing in less money rather than more. Also, there’s a pretty strong case that telling bidders you’re running a second-price auction but then not doing that is fraud.

  • Monotone dualization (\(\mathbb{M}\)) encompasses a family of equivalent computational problems that include converting logical formulas between conjunctive normal form and disjunctive normal form, and listing all minimal hitting sets or all minimal set covers of a finite family of sets. It has many applications, one of the more famous but less serious being its use in the computational proof that there is no valid 16-clue sudoku puzzle. From the point of view of theoretical computer science it is interesting for another reason: It can be computed in quasi-polynomial time (in the combined input and output size) but neither a polynomial time algorithm nor a hardness reduction explaining why it might be non-polynomial is known. Now the subject of a new article on Wikipedia.

  • Ramen geometry puzzle by Mark Andrew Gerads: if you have two square packs of ramen, and you split one of them into two equal rectangles, how big a circular pot do you need to hold them both?

  • A mathematician with a similar name to mine has also studied Egyptian fractions (\(\mathbb{M}\)): ring theorist Neil Epstein of George Mason University has two preprints on Egyptian integral domains and Egyptian rings, systems of numbers for which every fraction can be written as a sum of unit fractions (possibly required to be distinct). See also an earlier preprint by Guerrieri, Loper, and Oman. For instance, as GL&O note, \(\mathbb{Z}[\sqrt2]\) is Egyptian, because one can replace any irrational numerator \(a+b\sqrt2\) of a fraction by \((a^2-2b^2)/(a-b\sqrt2)\), express the new integer numerator as a sum of distinct unit integer fractions, and divide these all by the common denominator. However, \(\mathbb{Z}[x]\) is not Egyptian, because there is no way of expressing \(x\) as a sum of unit fractions.

  • A recent proposal in Nature to allow multiple simultaneous journal submissions (\(\mathbb{M}\), via) must have been written by someone in a field where reviewing involves glancing over a paper and guessing at its significance rather than careful in-depth checking of mathematical proofs. Looking up the author, he appears to be a psychologist. Check.

  • New Introduction to Probability for Computing book by Mor Harchol-Balter (\(\mathbb{M}\)). Chapters free to download for personal use.

  • Plate lattice architectures. Alison Martin makes 3d compressible and expandible structures from modular origami.

  • Another Wikipedia editor, Thomas Preu, has finally started a Wikipedia article on the Weisfeiler–Leman algorithm (\(\mathbb{M}\)). This algorithm finds canonical colorings of \(k\)-tuples of vertices in graphs (which can in turn be used for graph isomorphism) by refining the labeling using the colors of the vertices’ neighbors. I’ve had a browser bookmark for a long time (maybe years?) reminding me to do this, pointing to “The Power of the Weisfeiler–Leman Algorithm to Decompose Graphs”, by Kiefer and Neuen, but it seems Preu has saved me the effort.

  • Mike Vollmer asks: What is the current state of the art for making beamer presentations accessible? So far there are no useful answers, so if you know, please let him know.

  • Egan conjecture holds (\(\mathbb{M}\)), preprint by Sergei Drozdov. This is a tight inequality between the inradius, circumradius, and distance between centers of simplices in arbitrary dimensions, conjectured by Greg Egan in 2014.