Fall 2023. Tuesdays and Thursdays 11:15-12:30, Room SEC 1.321
Instructor: Boaz Barak
syllabus - schedule - background - Textbook - Gradescope - Canvas - Ed - Perusall
If you are taking CS 121 in the Fall of 2023, make sure to: (1) Do homework zero before the first lecture or at latest by end of first week. (2) Join the various platforms: Ed and Perusall. You can reach these from the Canvas. (3) Read the first two chapters on Perusall: introduction and mathematical background no later than by Monday September 4, 2023. (4) Read the syllabus for this course, and acquaint yourself with our schedule.
Computation occurs over a variety of substrates including silicon, neurons, DNA, the stock market, bee colonies and many others. In this course we will study the fundamental capabilities and limitations of computation, including the phenomenon of universality and the duality of code and data. Some of the questions we will touch upon include: Are there functions that cannot be computed? Are there true mathematical statements that can’t be proven? Are there encryption schemes that can’t be broken? Is randomness ever useful for computing? Can we use the quirks of quantum mechanics to speed up computation?
For a high level overview of much of what we’ll see in this course, you could do far worse than read Bernard Chazelle’s wonderful essay on the Algorithm as an Idiom of modern science.
See Fall 2023 student evaluations. (See also evals from 2022, 2019 , 2018, and 2017.)
The textbook for this course is Introduction to Theoretical Computer Science / Boaz Barak, which is a book in preparation that is available freely online. See the background page for some useful resources on the mathematical background.
In addition the following books can be helpful:
Quantum Computing Since Democritus / Aaronson. This book offers a free-flowing overview of many of the topics we will cover in this course (as well as several we won’t), and is an easy (and often entertaining) read. Reading this book over the summer can be a pleasant way to prepare for the course. From the back cover: “I laughed, I cried, I fell off my chair - and that was just reading the chapter on computational complexity.”, Seth Lloyd, MIT.
The nature of computation / Moore and Mertens. This monster (900+ pages) of a book contains a wealth of information on computation from a unique perspective. While reading it cover to cover is a large undertaking, it is a great book to sample from and have by your side as a reference (or as a makeshift monitor stand).
Introduction to the theory of Computation / Sipser. This was the textbook for CS121 in previous iterations. It is an extremely well-written book with very clear explanations and proofs, and can serve as a good accompaniment for about half of this course.
Computational complexity: A modern approach / Arora and Barak. This is a graduate textbook on computational complexity, and hence contains much more than what we’ll cover here. However, it might serve as a useful reference for some of the topics of this course (especially in its second half).
Mathematics and Computation / Avi Wigderson. This is a broad overview of the connections between mathematics and the theory of computation, covering some of the topics of CS 121 as well many advanced topics. It can be a great read for students that want to go beyond CS 121 and explore the theory of computation in more depth. The book will be published by Princeton University Press, and an electronic copy of it is freely available online.
Summer reading suggestions: Though not directly related to this course, another fun summer read which is good for math background in general (and not just specific to this course) is the book How not to be wrong by Jordan Ellenberg. Yet another very short but highly recommended general math book is Mathematics: A very short introduction by Timothy Gowers.
You might also find the following courses with online slides or lecture notes useful: