About this course

Following are a set of informally questions that this course attempts to address:

1. Is recognizing/verifying the solution easier than finding a solution under restricted resources (time/space) ?

2. Can efficient sequential procedures be made parallel ?

3. Can every randomized algorithms be made deterministic with a small slowdown under restricted resources (time/space) ?

4. A counting argument of Shannon shows that majority of the Boolean functions on $n$ bits are hard to be computable by Boolean circuits of $poly(n)$ size. Can we give an explicit description of such a hard Boolean functions ?

5. Does there exists a short verifiable proof for unsatisfiability of a Boolean formula ?

The overall course explores the above questions split in the following themes:

• Diagonalizationm, Completeness and Hierarchy theorems for deterministic/non-deteminisitic time and space.
• Basic complexity classes and containments. Link to complexity zoo.
• Polynomial hierarchy
• Randomized computation (in time and space settings)
• Counting complexity
• Interactive proofs
• Parallel algorithms for bipartite perfect matching
• Boolean circuit lower bounds
• Pseudorandomness and Derandomization, Pseudorandom generators
• Yao’s XOR lemma, Goldreich-Levin theorem
• Hardness versus Randomness

Links to similar courses

• Valentine Kabanet’s course page
• Dieter van Melkbeek course page
• Ramprasad Saptarishi’s course page
• Prahlad Harsha’s course page
• Luca Trevisan’s course page
• Ryan William’s course page
• Gil Cohen course notes
• Mark Bun’s course page