6.045/18.400  Automata, Comput, & Complexity

Final exam solutions posted

Hi class,

Solutions for the final exam are posted as "Final exam solutions" under "Materials > General" on Stellar.

Have a great summer!

Alan

Announced on 23 May 2014  10:52  p.m. by Alan Xinyu Guo

Textbook references

Hi class,

Here are some pointers to textbook readings most relevant for the topics we covered in the second half of the course (Sip means Sipser 3rd Edition and AB means Arora and Barak):

-Randomness: Sip 10.2, AB 7
-Cryptography: Sip 10.6, AB 9
-Interactive proofs: 10.4, AB 8.1 - 8.4
-Counting: AB 17.1 and 17.2, and 17.3 for definition of #P-hardness
-Approximation: Sip 10.1, AB 11.1, 11.2
-Quantum: 10.3, 10.7
-Polynomial Hierarchy: Sip 10.3, AB 5

Also, I strongly encourage you to have discussions on Piazza if you have any questions about a topic. Students are encouraged to answer each other's questions - this is a great way to check that you understand something yourself, and the act of writing out an explanation clearly so that someone else can understand it forces you to think clearly about the subject yourself.

Alan

Announced on 15 May 2014  5:50  p.m. by Alan Xinyu Guo

Review session tomorrow

Hi class,

Tomorrow I will be holding a review session instead of office hours, at the usual time (4-6) in my office or right outside my office, depending on attendance.

Alan

Announced on 13 May 2014  8:16  p.m. by Alan Xinyu Guo

Problem Set 6 Solutions Posted

Hi class,

PS6 solutions are now on Stellar (though grades are still not up).

Alan

Announced on 13 May 2014  8:15  p.m. by Alan Xinyu Guo

Reminder: Subject Evaluations

Hi class,

We strongly encourage you to enter the subject evaluations for 6.045. The link is here: http://web.mit.edu/subjectevaluation/

Your feedback, particularly open-ended comments, is important and taken seriously, so please do take the time to fill these out. This term the new form is shorter, and should take less than 5 minutes to complete.

Thanks,

Alan

Announced on 13 May 2014  10:50  a.m. by Alan Xinyu Guo