Another long year stuck inside. I graduated finally, and got a real job!
Computational Complexity: A Modern Approach (Arora, Barak)
Controversial opinion, but I don’t love the book. Its just okay. Proofs are often incomplete just to give the main result. The tone also sounds bored. Where it does succeed is that is has great references to more specialized material. I don’t know of a more modern graduate resource for complexity.
Recursive Function Theory and Logic (Ann Yasuhara)
The classic book “Formal Languages and their Relation to Automata” contains the following sentence in the references. “The unsolvability of Post’s correspondence problem was shown by Post in [1946]. For an easy alternative proof of PCP see Floyd [1964b]. The paper by Floyd actually appears to be some technical manuscript of a few pages. I can’t find any version of it online, even for sale. The closest hard copy is 500 miles away at the Carnegie Mellon Library. Its also available through the military if I were to pay for a FOIA request. I don’t have that kind of money, so what I did was look up every single book which cites it, and buy the cheapest one on ebay for four dollars, which happened to be this book! Yasuhara’s book proves PCP very early on, and contains the confirmatory footnote: “Although this problem was first proposed and shown to be unsolvable by Post (1946), the presentation here follows from Floyd (1964)”. The proof I have been searching for is based on the unsolvability of the word problem for Semi-Thue systems, as compared to the method of computation histories. The proof idea is similar in spirit, so I didn’t learn some magical new technique, but I did learn about this book. Its really good! Full of great problems and little anecdotes. Notation can be a bit crowded but it presents deep ideas in a clear manner.
Logicomix
This is a graphic novel about the life of Bertrand Russell, with many side characters, Wittengenstein, Godel, Von Neumann, Cantor. I love to tell the story of How Godel owned Russell & Whitehead, or how Turing owned Hillbert. Its something pretty dramatic. This is a book on that level of drama. No spoilers.
Foundations of Distributed Consensus and Blockchains
These are class notes by Elaine Shi. I always find myself coming back to them, and every time I do, they are longer, and more detailed. They are being turned into a full book. For the current blockchain class, we say we use a book, but its not that good. So we really don’t use one. Few years from now, I would hope this to become a standard book. The title is probably working.
Origins of Recursive Function Theory (Kleene)
Steven Kleene gives four decades of history. Full of nothing but anecdotes, even some photos.
E-mail and the unexpected power of interaction
Another large summary, how the gold rush to prove IP=PSPACE developed over a mailing list in 1989.
Security Analysis of Quantum Lightning
This has got to be the worlds shortest accepted paper, from Eurocrypt 2021. The document is 6 pages, 4 pages are summary, and the technical contribution is less than a page. The short answer is, it found a nuanced way to break an exotic hardness assumption.
Threshold Secret Sharing Requires a Linear-Size Alphabet
Supposedly this technique was known from 2016, but the paper appeared in 2020. They prove lower bounds on secret share sizes using game theory! Very very interesting technique, also hard to digest.
Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits
Halfgates is a technique by Mike Rouslek (et al) where they show how to do non linear gates in a garbled circuit for . That was the current state of the art. There were even results to suggest it was optimal. This work lowers it to by tweaking the model some. The idea needs just a little linear algebra.
The Acrobatics of BQP
Quantum complexity theory is actually really boring, except this paper. It solves an open conjecture by Fortnow, with a negative answer, if quantum-ness is separable, like random-ness is.
I have read many many more papers this year, these were just the few I found significant enough to mention.