Linkage

Possibly all the ways to get loop-finding in graphs wrong (\(\mathbb{M}\)). Simon Tatham tries various ways of finding the edges of a graph that belong to at least one cycle, with bugs of various levels of sophistication, until finally settling on Tarjan’s bridge-finding algorithm. The application: checking puzzle solutions.

Using polyhedral combinatorics to compute the probability of cyclic preferences in a multiway election (\(\mathbb{M}\)).

AI is somehow even worse at drawing soccer balls than it is at hands.

We don’t know whether minor-closed graph families have bounded book thickness. Statements of this in the literature rest on book embeddings of graphs of bounded non-orientable genus, claimed long ago by Heath and Istrail but never detailed. David Wood’s student Eric Luu tracks down two references pointing out the problem.

A puzzle asking for a gappy packing, of three unit equilateral triangles and three unit squares into a hexagon with 120° angles and side lengths alternating 1–2–1–2–1–2. Spoiler for solution.

“Generative AI has polluted the data. I don’t think anyone has reliable information about post-2021 language usage by humans” (\(\mathbb{M}\)). From a post by Robyn Speer explaining why the wordfreq tool will no longer be updated.

Lance Fortnow on the award of the Physics Nobel for neural nets: “Physics wants to make its claim on AI. For as they say, success has many parents (and failure is an orphan).”

Gareth Edwards predicts that the recent transfer of sovereignty over the Chagos Islands from the UK to Mauritius will lead to the demise of the .io domain (\(\mathbb{M}\), via). Since my blog is hosted by github.io I am somewhat concerned about this possibility, but the MF commenters seem to feel it is unlikely. Relatedly, from a link in the comments: five past removals of two-letter country-code top-level domains were .yu, .tp, .zr, .an, and .um. “The fact that ICANN hasn’t acted to remove .su from the root, thirty years after the Soviet Union collapsed, could be seen as precedent.”

Good news: Australian government sues Chegg (\(\mathbb{M}\)) for violating Australia’s strict laws against cheating providers.

Blockchain buzzword bingo as an example of how CACM has become terrible again under the editorship of James Larus. That’s not even its worst: see also straight-up Trumpist propaganda.

Applications of group fairness to the assignment of reviewers in large conferences (\(\mathbb{M}\), via). The goal is to assign reviewers in such a way that no subcommunity feels it would be better off making its own splinter conference. Subcommunities are not part of the input; they are an emergent feature of the model. The model of reviewing is a little oversimplified: all papers are single-author, the only conflicts of interest are with one’s own papers, there is a strict threshold of accepting scores that leads to acceptance, and only author preferences for reviewers rather than reviewer preferences for what to review are considered. And there is no consideration of the possibility that allowing authors power in selecting their preferred reviewers is a recipe for quid-quo-pro behavior and refereeing cartels. Still, I think it’s an interesting idea.

Rhombille tiling on a manhole cover, Morecambe, Lancashire, England.

I’m sure many have seen the Stallman Report detailing Richard Stallman’s misconduct and how it and his enablers have harmed the free software movement (\(\mathbb{M}\)). Much of this is not new but I was still shocked by a line early in the “Why publish this report?” section: “Women represent just 3% of the free software community, compared to 23% of industry programmers generally.” Obviously not all of that disparity can be attributed to Stallman alone, but his continued position of prominence is a symptom of a broader disease in the community’s culture. Paying attention to these problems rather than turning a blind eye to them is a necessary step towards healing.