Instructor |
Hamed Hatami | |

TA |
Lianna Hambardzumyan lianna.hambardzumyan@mail.mcgill.ca | |

Lecture |
Tuesday-Thursday 11:35am - 12:55pm (Maybe Eventually McConnell Engineering Building 304). | |

Outline |
course outline | |

Office hours: |
Tuesday-Thursday 14:00 - 15:00 on zoom |

- Last Updated Jan 21, 4pm: Lecture 0-4 are posted.

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

** Complexity Background:** I will start the first lecture assuming that everybody is familiar with Turing Machines, Undecidability, P, NP, CoNP, EXP, reductions, NP-completeness to the extend that they are covered in Comp 330. If you feel that you have forgotten some of these topics, it is useful to quickly review them before the first lecture.

** Probabilistic method background:** Some of the proofs in this course use probabilistic arguments. I will assume that you are familiar with elementary discrete probability theory: Discrete Random variables, Expected value, Variance, Linearity of expectation. If you feel rusty about these topics, I suggest reading the first two (or even better: four) chapters of the excellent book, * the probabilistic method* by Alon and Spencer.

**Linear programming background:** We might come across some arguments based on the linear programming duality. If you have not seen this topic in Comp 360, you can do some preparation ahead of time by reading these two short lecture notes Linear programming, and Linear programming duality.

*Homework (80% = 4 x 20%).*
There will be four homework assignments. The due dates are going to be announced. ** The homework 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.

* Group project. 20%*

Late homeworks can be submitted until 96 hours after the deadline. There will be a penalty of -10 (out of 100) points for a two-day delay, and -20 points for four-day delays on late homeworks unless a valid reason is provided by the student. Some personal circumstances for which accommodation may be warranted include, but are not limited to: Student illness (mental/physical), Family/partner illness, Death in the immediate family or of a person with whom the student has a similarly close relationship, Religious Observances, Pregnancy, Delivery of a child, Parenting issues.

The following are reasons for which an extension request will normally **NOT** be granted: Employment reasons, Travel/vacation/social plans, Airline flights and schedules, Other assignments and exams due on or about the due date.

* Class participation:* Although not a formal component of the course grade, active participation can effect your grade in a positive way.

- Hierarchy Theorems: Time and Space. Polynomial Hierarchy.
- Space complexity: L, NL, Immerman-Szelepcsenyi, Savitch's Theorem, NL=coNL, Branching programs
- Circuits: Relativization, Basic Circuit Complexity, P/poly, Karp-Lipton, Shannon's theorem
- Circuits: Depth, NC, AC, Razborov-Smolenski, Hastad's switching lemma. Parity not in AC0
- Monotone Circuits: CLIQUE not in monotone P.
- Randomness: BPP, RP, ZPP, BPP in PH, BPP in P/poly
- Counting classes, #P, Toda's theorem.
- Interactive proofs, MA, AM.
- PCP theorem. Hardness of approximation

- Sipser
*Introduction to the Theory of Computation*for the background material. - Wigderson
*Math and Computation*for a beautiful, high-level and nontechnical exposition on the relation between mathematics and the theory of computation, and the importance of many of the topics covered in this course. - Additional reading: Aarora and Barak
*Computational Complexity - A Modern Approach.*

Lecture |
Topic |
Recommended Reading |

0: Jan 7 | No class. The first lecture is going to be on the 12th. | Chapters 1, 2, 3 of Math and Computation. |

1: Jan 12 | P vs NP. Time and Space Hierarchy Theorems. | |

2: Jan 14 | Polynomial Hierarchy. | |

3: Jan 19 | Space complexity | |

4: Jan 21 | L, NL, Savitch's theorem. | |

5: Jan 26 | Immerman-Szelepcsenyi theorem (NL=CoNL), P and Circuits | |

6: Jan 28 | Circuits, P-complete, and NP-complete problems. | |

7: Feb 2 | Circuits, Formulas, and Depth. Depth bounded by long of formula size. | |

8: Feb 4 | AC, NC classes and their relation to NL, L. | Finishing the notes from lecture 10 |

9-10-11-12 | Alternating Circuits, Switching Lemma, Razborov-Smolensky | Notes. |

13-14 | Razborov's lower-bound for monotone circuit size of clique. | |

15-? | TBA |

*Academic honesty.* McGill University values academic integrity. Therefore all students must
understand the meaning and consequences of cheating, plagiarism and other academic offenses 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.