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

**Instructor:**Boaz Barak

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

**NEWS:**

Please fill out the CS 121 survey!

The Fall 2017 offering of this course will be significantly revised from previous iterations. Please see this page for the recommended mathematical background for this course.

I highly recommend all students complete

**homework zero**before the first lecture on August 31 or at least no later than Wednesday, September 6th.piazza website is available for sign in - every student that wants to take CS 121 should join it!

On

**Friday Sep 1st 1pm in the ground floor Maxwell-Dworkin lobby**we will have a**CS 121 meet the staff party**with free Pizza and refreshments. It will be a good chance to get to know the lecturer and TFs, as well as meet up other students and potentially find problem-set partners.We will have an optional two part

*proof workshops*on the week of September 4th and September 11th (more information to be announced later). These will give students a chance to sharpen their proof-writing skills.Please read the syllabus carefully for course policies and information.

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 will have 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 the first half or so 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.