It has been a really long year, forced inside. Since I don’t have to bike to an office everyday, I found myself with a lot more time for reading. Here is some of what I read this year, mostly in the order that I read it.
MIP* = RE (Several Authors, 2020)
A new result in complexity! MIP* is the class of languages with multi-prover interactive proof systems. MIP* adds the power of entanglement. The provers are all quantum computers sharing entangled qubits, and decision must come in polytime. RE here stands for the recursively enumerable languages. What initially drew me to the paper was the weight of the result. I was planning on only skimming it, as it is over 200 pages. Instead I sat down and read the whole thing in a week, and I fell behind a bit in class because of it. What I love is that the whole paper is entirely self contained. This can be rare for new theorems. They usually have to build upon mounds of previous work.
Syntatic Structures (Noam Chomsky)
I finally decided to read this. It was shorter than I thought, and only took me a day.
Introduction to the Theory of Computation (Michael Sipser)
This is probably the fourth time I have read this book cover to cover. It is used in every undergrad complexity/automata/computability course at every school. I am not 100% in agreement in the way certain things are presented. For example, instead of set “cardinality”, the word used is “same size”. But talking with the author, these decisions are deliberate. Also as a TA, these decisions definitely make the material more available to CS students. This book remains on my desk as a permanent reference, and mouse pad.
Computability and Unsolvability (Martin Davis, 1958)
I read this book for a few reasons. First, I was looking for another computability book. I wanted to see what a graduate presentation of the same material could look like. I chose this book for its age. I wanted to see presentation of the material before the development of complexity. I had a gut feeling that in more contempory material, the halting problem is presented as a reduction to warm up to the concept of polytime reductions for NP-completeness. I learned a lot. Recursive functions, godel numberings. It took some significant work to eat this book, having to reference previous sections often. I also chose this book compared to other old books because it was cheap on ebay for a hard copy.
Formal Languages and Their Relation to Automata (Hopcroft & Ullman, 1969)
Another common textbook. I had not read this one before, but it is cited on nearly every wikipedia page. I think this created some hype around it. I found the book to be quiet boring. The coverage of the material was good, I had nothing to disagree with. It was just things I have seen already everywhere else. I did like that the references were mentioned in human english, saying which sources contained what. I wish I had found this book maybe earlier in my education.
Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits (Several Authors, 2020)
When I first read this paper, it was not called “wolverine”. Basically, new state of the art in the garbled circuits arms race. It beats all prior work in time, and memory significantly. It actually took me some time to understand what was going on.
Abstract Algebra (Dummit & Foote, 2003)
I took graduate abstract algebra this Fall. I have previously taken undergraduate algebra, and a many tangential classes, like algebraic topology. I was more familiar with the book by Herstein, so going through this book was new. I don’t have much to say about it. I just think it is noteworthy because we went through the entire book at lightspeed all online, and I am proud of that.
In Praise of Idleness, (Bertrand Russell, 1932)
This essay is only a few pages. I think that idle time is never really idle. Humans, given the space will find ways to do all sorts of constructive things. Write books, or build statues from toothpicks. I also think that idle time is the best time for scientific inquiry. My best ideas come when I am sitting by a fire, or taking a walk, or just falling asleep. They certainly don’t happen at a desk. If you are stuck working 8+ hours a day, how will you ever find time to build a giant home-made telescope, or invent a new kind of chocolate cake? This is what society should place value on, instead of trying to sell more ads. Giant home made telescopes, and chocolate cakes.
From Mathematics to Philosophy (Hao Wang, 1974)
I read this book only for one reason. Some time later in his life, Godel wrote a letter on, perhaps a flaw or disagreement with the construction of Turing machines. This letter was handed to Hao Wang, who published a copy in this book. I ended up reading the whole thing. It was not exactly what I was used to. There is a thesis the author has, and presents material to support that thesis. This is not what I am used to, from science atleast.
A Brief History of Time (Steven Hawking, 1989)
Every time a physics Nobel, Turing award, or Godel prize is anounced, I try to understand the body of work for the prize. This year, Roger Penrose won for his work on black holes, which is the contents of the first half of this book. Hawking states in the introduction that for every equation he were to include, the sales would half, so he only includes one equation. I wish there were more. A lot of the cool parts of physics are taking some equation, and trying to see what it means physically. Consider the Lorentz transform: . As , for things we normally observe, this factor becomes extremely close to 1, so it could have easily been hidden in error. As v approaches c, then this factor approaches 0. My favorite section of the book was chapter 9, the arrow of time. I had never bothered to ask why time goes forward and not backwards also. Seems like a silly question. The book also defined for me a concept which I had been thinking about, but did not know had a name: The anthropic principle.
Godel, Escher, Bach (Hofstadter, 1999)
I had big art book of the collected works of M.C. Escher when I was a kid. I am certain that the art in the book helped me think spatially. Also in my college career, I have become quiet familiar with Godel. I certainly enjoyed this book.
Introduction to Mathematical Philosophy (Bertrand Russell 1928)
I read this book because I heard he wrote it from jail, and that sounded cool. It would actually be a nice text for a freshman discrete math course.
Collected Fictions (Jorge Luis Borges, 1998)
I found a copy of the short story “Library of Babel” online. I liked it enough I wanted to read more by the same author. I like that the stories are short, and I don’t need to maintain object permanence going from one story to another.
A Shorter Model Theory (Wilfrid Hodges, 1997)
I am still working through this book, but am through the majority of it. The problems, I think are a little tough for me. I chose to self study from this book because I wanted a challenge. For me, this was not just an introduction to model theory, but solid training in logic.
I spent a lot of time reading this year. For my distributed systems course, and my quantum computing course, I had to read a lot of papers. In total, I think I read maybe 100 papers this year. This list is just what I found worthy of note. I have plans for more, since we aren’t coming out of this apocalypse anytime soon. In the near future, I want to understand Cohens proof by forcing of the independence of CH, and I want to finish the Hodges book fully.