Linkage

Graduata data structures online (\(\mathbb{M}\)), finally done and graded. Warning: dry voice-over-slides videos, and some mistakes, because I didn’t have time to put together anything more sophisticated or edit more carefully.

Freedom of the press under attack: 100+ times law enforcement violently assaulted journalists in US at George Floyd protests (\(\mathbb{M}\)). Of course this is only a small piece of an enormous pattern of awfulness by the current administration, law enforcement, and the prison-industrial complex, but it’s a piece that I think is important to document.

Four book publishing corporations claim that what libraries always have done (lending out copies of books they have purchased as physical objects) is illegal, because computer, and are suing the Internet Archive over it (\(\mathbb{M}\), via, via2). One of them, Wiley, is also a major publisher of academic works. Perhaps that should give some of us pause in which journals we send our papers to and referee for.

Moiré patterns from random dots (\(\mathbb{M}\)). Overlaying the same random dot pattern on a translated and rotated copy of itself shows concentric dots around the center of rotation, illustrating Chasles’ theorem that every rigid transformation of the plane is a translation or rotation. The effect seems to have first been observed by Leon Glass in “Moiré patterns from random dots” (Nature, 1969).

“The Micro-world of Cographs”, Alecu, Lozin, and de Werra, IWOCA 2020 (\(\mathbb{M}\)). Cographs have a simple structure, but there’s still an interesting hierarchy of subclasses of graphs within them restricting different parameters of graph complexity to be bounded. A typical result: Every cograph with large h-index must contain a large complete graph, balanced bipartite graph, or forest of many high-degree stars.

Japanese scientists use kirigami to design a shoe sole with pop-up non-slip spikes.

Ombre et lumière. Artwork in which random-looking blocks on a wall create a recognizable shadow in side-light.

Brian Hopkins answers his own 9-year-old question on the history of Fibonacci numbers and compositions (\(\mathbb{M}\)). The ancient Indians knew that compositions (ordered partitions of integers) into \(1\)’s and \(2\)’s are counted by Fibonacci numbers. For instance, there five ways of forming \(4\) as an ordered sum of \(1\)’s and \(2\)’s: \(2+2=\) \(2+1+1=\) \(1+2+1=\) \(1+1+2=\) \(1+1+1+1\). Cayley knew that the compositions with all parts bigger than \(1\) have Fibonacci counts. But who first knew that compositions with all parts odd are also counted by Fibonacci? Hopkins suggests: de Morgan, 1846.

Despite new US covid cases being more or less the same level (or worse) as the start of the lockdown in March, some universities are telling their students that it’s safe to return to normal and at the same time telling their faculty that unless they’re close to retirement age and have additional medical conditions, they must teach face to face (\(\mathbb{M}\)).

A nice page of recent writings about abstract strategy games, mostly connection games (\(\mathbb{M}\)).

MIT gives up on trying to get an equitable subscription deal from Elsevier, ends negotiations (\(\mathbb{M}\), via).

The Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) (\(\mathbb{M}\)), newly published open-access through LIPIcs. Sadly, the conference will be online rather than in the Faroe Islands as originally planned. The Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020) is also now out.

Illuminate (\(\mathbb{M}\)). An online puzzle based on the art gallery theorem, part of the media exposition of this year’s Symposium on Computational Geometry. See also the theoretical writeup.

Skiena’s Algorithm Design Manual (\(\mathbb{M}\), via, via2, see also), one of 500 Springer textbooks still available for free download from the publisher.