| Instructor | Hamed Hatami | |
| TA's | Teaching assistant: Ben Cheung (tsun.ming.cheung@mail.mcgill.ca) | |
| Lecture | Monday, Wednesday 11:35-12:55 at BURN 708 | |
| Course Outline | Download | |
| Office hours: | Wednesday 14:40-15:40. If you want to meet outside office hours, the best thing is to send me an email, but you can also just drop by my office, and if I'm not busy I will answer your questions. | |
| Lecture notes: | Here is a draft of the Lecture Notes. It will be updated as we go. |
| Part I | ||
| Lecture | Topic | Reading |
| 1 (9/7) | Computational model, Time and Space classes | Chapter 1, Chapter 2 of notes until the beginning of time Hierarchy Theorems. |
| 2 (9/12) | Time Hierarchy Theorems, Polynomial Hierarchy. | Chapter 2, Chapter 3 |
| 3 (9/14) | Space complexity. | Chapter 4 |
| 4 (9/19) | Savitches theorem. | Chapter 5 |
| 5 (9/21) | NL equals coNL. | Chapter 6 |
| 6 (9/26) | Oracles and relativization | Chapter 8 |
| 7 (9/28) | Probabilistic complexity classes: RP and ZPP | Chapter 9 |
| 8 (10/05) | Probabilistic complexity classes: BPP | Chapter 9 |
| 9 (10/13) | The class PP, P/Poly | Chapter 9 |
| 10 (10/17) | P/Poly | Chapter 10 |
| 11 (10/19) | NC and AC, switching lemma | Chapter 11 |
| 12 (10/24) | Lower bounds against AC^0, Influences | Chapter 11 |
| 13 (10/26) | XOR gates, Razborov-Smolensky | Chapter 12 |
| 14 (10/31) | Razborov-Smolensky, start of monotone circuits | Chapter 13 |
| 15 (11/02) | Monotone circuit lower bound for clique | Chapter 13 |
| 16 (11/07) | Natural Proofs | Chapter 14 |
| 17 (11/09) | Natural Proofs + Fourier analysis | Chapter 15 |
| 18 (11/14) | Fourier analysis of Abelian groups | Chapter 15 |
| 19 (11/16) | LMN: PAC learning of AC0 under uniform distribution | Chapter 16 |
This is a rigorous course with an emphasis on mathematical proofs. This course is a continuation of Comp 330 and as a result it requires Comp 330 as a prerequisite. You must be comfortable with basic concepts from logic, linear algebra, Turing Machines, and you must be able to read and write precise mathematical statements.
Homework (80% = 4 x 20%). There will be four homework assignments. The due dates are going to be announced. The homework and the exams will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. Your grades will be posted on mycourses.
Late homeworks can be submitted for valid reasons.
Group project. 20%
Academic honesty. McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, allowing others to copy your work, will not be tolerated, and they will be reported to disciplinary office.
Submission of written work in French. In accord [sic] with McGill University's Charter of Students' Rights, students in this course have the right to submit in English or in French any written work that is to be graded.