6.045/18.400 Automata, Comput, & Complexity
Spring 2013
Instructor: Scott Aaronson
TAs: Arturs Backurs, Shalev Ben David
Lecture: TR2.30-4 (32-141)
Information:
[Alan
Turing's 1936 paper "On Computable
Numbers"]
This course provides a challenging introduction to some of the
central ideas of theoretical computer science. Beginning in
antiquity, the course will progress through finite automata,
circuits and decision trees, Turing machines and computability,
efficient algorithms and reducibility, the P versus NP problem,
NP-completeness, the power of randomness, cryptography and one-way
functions, computational learning theory, and quantum
computing. It examines the classes of problems that can and
cannot be solved by various kinds of machines. It tries to
explain the key differences between computational models that
affect their power.
Prerequisites: We assume that you have taken 6.042 Mathematics for Computer Science, or have equivalent mathematical preparation. In particular, we will assume you have basic "mathematical maturity": i.e., that you're comfortable both reading and writing rigorous mathematical proofs.
Textbooks:
1. Introduction to the Theory of Computation by Michael Sipser -- covers most material from the first half of the course
2. Optional:
Quantum Computing Since Democritus by Scott Aaronson
3. Optional: The Nature of Computation by Cris Moore and Stephan Mertens
4. Optional: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak -- covers most material from the second half (as well as more advanced material that we won't get to in class). Draft available for free on the web.
See the 6.045 Curricular Goals Map giving a dynamic graphical display connecting the class outcomes with the outcomes of other subjects in the Course 6 curriculum.
Announcements
Final exam grades
As some of you might have seen already, all the grades are now up on Stellar for everyone who took the final today. Some statistics: the mean was 117.2 (out of an absolute maximum of 200), the high score was 166, the low scores were in the 70s, and the standard deviation was 25.6. This is better than I was expecting! After seeing the pained expressions on people's faces this morning, I told Arturs and Shalev that I guessed the mean would be somewhere around 100. Also, like with the midterm, there were no long-answer questions that no one managed to solve correctly. We haven't yet done the course grades -- except in unusual circumstances, we plan to submit them by Friday -- but for calibration purposes, you might want to know that the average course grade in past years has consistently been a B.
Important: There are 4 students who have yet to take the final exam. So please do not post anything about the exam on Piazza (and, obviously, don't discuss the exam with any student who hasn't yet taken it).
Some other loose ends: Arturs and Shalev will prepare a typed answer key to the final, for those who are interested. You're also welcome to pick up your final from my office next week, later in the summer, or even in the fall if you still care then and I can still find the exams. :-) For various reasons, we can't give them back this week, but you can come tomorrow or Friday to review your final in my office if you really can't wait. Just send me an email to make sure I'll be around.
The graders are also hard at work on pset6, and will be finished grading it by tomorrow. I sincerely apologize that we weren't able to get pset6 back to you before the final -- that was a significant screwup on our part. Once it's ready, pset6 will also be available for pickup from the pset boxes outside my office.
Anyway, thanks so much to all of you for sticking with this class till the end! You were awesome, and I hope you enjoyed taking the class at least Ω(1/poly(n)) as much as I enjoyed teaching it. Have a wonderful summer.
All the best,
Scott
Announced on 22 May 2013 8:27 p.m. by Scott Aaronson
Final exam reminder
Just a reminder that the final exam will be tomorrow 9AM-12PM (starting promptly, so I strongly recommend getting there by 8:50), in room 50-340, the Walker Memorial 3rd floor gymnasium:
http://web.mit.edu/registrar/classrooms/exams/rooms/Walker.html
If, for any reason whatsoever, you can't make this exam and/or require special arrangements, then please respond to this email today letting me know -- even if you've already done so. It would be helpful to me to have a complete list so that we can plan the makeup(s).
It was wonderful having all of you in the course. Good luck on the final!!
--Scott
Announced on 21 May 2013 10:42 a.m. by Scott Aaronson
Additional Office Hours
I will hold additional office hours on Monday from 1pm to 2pm in the G6 lounge.
Shalev
Announced on 16 May 2013 7:30 p.m. by Shalev Ben David
Extra office hours
Hi everyone,I will hold extra office hours this Friday at 3:30-4:30 pm in the G6 open space.
Best,
Arturs
Announced on 16 May 2013 12:24 p.m. by Arturs Backurs
Readings for Lectures 18-23
Lecture 18 - "Lecture 14: Probabilistic Complexity Classes" notesLecture 19 - "Lecture 15: Derandomization / Crypto Double Feature" notes
Lecture 20 - "Lecture 16: Private-Key Cryptography" notes
Lecture 21 - "Lecture 17: Public-Key Cryptography" notes
Lecture 22 - "Lecture 18: Cryptographic Protocols" notes
Lecture 23 - "Lecture 22/23: Quantum Computing" notes until section 2.2
Announced on 13 May 2013 10:49 p.m. by Arturs Backurs