Linkage

The logic of definite descriptions (\(\mathbb{M}\)). Joel Hamkins wrestles with logical formulations of “the”, indicating that a description uniquely identifies something. If you define a logical operator whose value is the thing identified by its argument, and use it in a context that doesn’t uniquely identify something, does your overall formula still have a truth value? Fortunately(?) the stakes are low: several plausible choices produce logics with the same power as classical logic.

DALLE paintings of people using quantum computers, in the styles of famous artists (\(\mathbb{M}\), via). I am superimpressed at how this sort of thing can be done quickly by software, rather than human artists with much more time.

Supersingular isogeny Diffie–Hellman broken (\(\mathbb{M}\), via). This cryptosystem relied on the unpredictability of supersingular isogeny graphs, expander graphs with vertices for elliptic curves and edges for certain morphisms between them. Apparently, these graphs are less unpredictable than thought. SIDH and the SIKE protocol built on it were hoped to be impenetrable to quantum computers but the attack does not use quantum.

The warped grids of Dana Piazza’s artworks look like curvy woven textiles (\(\mathbb{M}\)).

\(10^5\)fold speedup for Matt Parker’s Wordle puzzle (\(\mathbb{M}\)). This has nothing to do with actual Wordle puzzles; it’s about sets of fiveletter words with no repeated letters (see Parker’s original video). Two ideas for the speedup: first, save a 5! factor by only searching sorted sequences of words. And second, make the repetition tests blazingly fast using 26bit bitvectors for the sets of characters already used, so repetitions can be found as a bitwise and.

Cute puzzle from Sándor Fekete’s 1992 dissertation, via Yan Gerard (\(\mathbb{M}\)): prove that any finite set of points in the plane has a simple polygon with all of the points as vertices, covering more than half of the area of its convex hull. More generally, polygons using all of a given point set as vertices are called polygonalizations, and there are many unsolved problems concerning them.

Prioritizing value (lightness and darkness) versus color (legibility of hue) in imaging (\(\mathbb{M}\)). With examples both from digital photo processing and the history of painting, and suggestions for how to achieve either desired effect in Photoshoplike editors. Daniel Dichter, 2020.

A philosophical/definitional question (\(\mathbb{M}\)): should “problem \(X\) on input class \(Y\) is \(\mathsf{NP}\)complete” mean there is a specialized decision problem whose valid inputs are exactly \(Y\) that is \(\mathsf{NP}\)compete, or should it mean that problem \(X\) (allowing wider inputs) is \(\mathsf{NP}\)complete and has hard inputs in $Y$?
Case in point: snarks (new Good Article on Wikipedia) are \(\mathsf{coNP}\)complete to recognize. Can it ever be correct to say “problem \(X\) is \(\mathsf{NP}\)complete for snarks”?

Interesting discussion on the repeated independent invention of zero as concept and as a digit in positional numbering, in many ancient cultures (\(\mathbb{M}\)), prompted by a dubious jingoistic Scientific American article (linked) that somehow assigns “ownership” (!?) of this concept to a Sumatran kingdom contemporary with medieval Europe, who somehow spread their knowledge backwards in time to the ancient world. What has happened to Scientific American?

Summer is a time for transitions among my UC Irvine theory colleagues (\(\mathbb{M}\)):

Sandy Irani went on leave to be associate director for the Simons Institute for the Theory of Computing in Berkeley.

Amelia Regan retired (emeritus) to direct the supply chain transportation & logistics graduate program in civil & environmental engineering at the University of Washington.

Dan Hirschberg also retired as emeritus, but is teaching on recall.
Congratulations, Sandy, Amelia, and Dan!


If you were thinking of submitting a paper to COCOA (the 16th Annual Conference on Combinatorial Optimization and Applications, previously scheduled with initial submission date August 12 and conference in Dallas Texas in December), as I was, think again (\(\mathbb{M}\)). It’s now been pushed back a year and planned to be onlineonly. I have no more information than what is linked here.

I’m sad that an article with the headline “Scientists Protest Censorship in Cosmology” (\(\mathbb{M}\), via) is only about fringe papers getting rejected as offtopic by arXiv and MNRAS. I wanted it to be about scientists holding big marches with signs in the street in opposition to the cosmic censorship hypotheses, that the universe conspires against scientists to make it impossible to see what singularities in spacetime look like.

David Cushing and Christian LawsonPerfect critique more OEIS sequences (\(\mathbb{M}\)).

A bar chart showing occupations for which the English Wikipedia’s coverage of women (as a proportion of biographical articles for that occupation) most improved over the five years from 2016 to 2021 (\(\mathbb{M}\)). I’m happy to see “scientist” (13% to 25%) and “professor” (11% to 20%) made the list. But they’re still a long way from 50%.