publications
posts
- 2026-07-13 ASP-completeness
- 2026-06-17 23
- 2026-01-22 Nash-Williams Proof Golf
- 2026-01-12 Dynamic (Δ+1) Vertex Coloring
notes
2026-07-14
$\text{ASP}$-completeness
MIT Hardness Group 2024 cite Yato and Seta 2003 for $\text{ASP}$-completeness. It turns out $\text{ASP}$, and $\text{ASP}$-completeness although without the name, was first defined in Ueda and Nagao 1996. The paper was available only as a postscript file, so I converted it to PDF, attached here for posterity and the common welfare.
I put some definitions about $\text{ASP}$ in this post.
2026-07-12
Eytzinger
Five months ago, almost to the day, I was reading (once again) about BFS-traversal order for BSTs (aka level-order, heap, and implicit BST layout). I had seen this in an early data structures class and not thought much of it, but it snuck up on me. At some point I was thinking about database index structures and cache-friendly searching, and after coming up with a couple of other ideas to benchmark, I had a gander through Gemini’s literature review, which pointed out this great blog post. Being a busy person with no time to waste, or maybe a pizza on the way, I skipped to the implementation and results, added a version of the layout to my inchoate benchmark, and moved on, noticing peripherally that this was the same as the BFS layout. The next day I opened the Khuong and Morin paper referenced by the post and checked out some of the results more closely, again skipping any preamble — these benchmarks (Claude agents) weren’t going to run themselves. My benchmarks more or less replicated the results in the paper, but I was curious where “Eytzinger” came from — I couldn’t find the name anywhere else.
Interestingly, it looks as if this paper is the first to attribute this layout to Michaël Eytzinger, who in 1590 described a nice method for writing out family trees (which tend to be binary) linearly, he too being a busy person, with no time to figure out how to print family-tree graphs, which outgrow the page quickly anyway. This also makes Eytzinger’s “Thesaurus principum hac aetate in Europa viventium” the oldest cited work in any CS paper I can find, appearing as [6] in the Khuong–Morin paper; see also the Wikipedia article.
(For the other close contenders — Leibniz citing Fuxi (“Fohy”), Pāṇini’s anticipation of BNF (apparently also known nowadays as PNF) by 2400 ± 100 years, references to Euclid plus a bunch of 19th-century French math papers — I wouldn’t call them “citations in CS papers”, although they’re good suggestions for anyone who wants to beat the record.)