Fall 2017. Tuesdays, Thursdays, 10am-11:30am, Geological Museum Hall 100

**Instructor:**Boaz Barak

syllabus - schedule - piazza - canvas - gradescope background - lectures - nand pl

**NEWS:**

This is the home page for the Fall 2017 offering of this course. The updated version for Fall 2018 will be posted on summer 2018.

See here for Fall 2017 student evaluations.

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.

This course has very extensive lecture notes but no official textbook. However, 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. 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.

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.

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).

See the background page for some useful resources on the mathematical background.