Basic Information
Instructor : Jayalal Sarma M.N.Office : FIT 4-606-3, Ph. 1683
Email : jayalal@tsinghua
Lectures : Mondays and Wednesdays, 1:30-3pm, at Room 1-222, FIT Building
Office hours dedicated for the course : Wednesdays, 3-4pm
About the Course
A (slightly advanced) course in Computational Complexity Theory. Computational Complexity Theory is the study of efficient computation and its fundamental limitations. The theory helps us to state questions about this in a precise way and provide qualified answers to them. To state some examples, how much resources is required to solve concrete computational problems? Does the use of randomness or parallelism make computations significantly faster? However, it turns out that the hardest thing to prove about the models is that they cannot solve a given problem within particular resource constraints. Such ``lower bounds'' are currently obtainable only when the model is very specialized or the constraints are very severe. Inherent limitations of the currently known techniques is also something that is currently explored on the research frontier of complexity theory.The course will give a quick introduction to the classical results and techniques in complexity theory and thereafter cover (selected) newer results and areas. The choice of topics is based on the view that the course should provide a platform for the current topics of research in the area of complexity theory. We might possibly be skipping some of the basic material in a standard complexity theory course. In general, we hope (or want) to touch upon most of the topics below roughly divided into 28-30 lectures in total. We may choose to slightly deviate (which I will indicate in italics) from this plan as the course progresses. I shall provide references to read up the topics that we skip.
- Classical structural complexity theory (4 lectures): Notion of a
resource. Time and space. Hierarchy theorems. Oracle Turing
Machines, relativisation. Reductions and Completeness. Complete problems
for various classes. Alternation. Polynomial Time Hierarchy.
Karp-Lipton-Sipser Collapse Theorem.
Skipped : Ladner's Theorem. Toda's theorem
- Nonuniform models of computation (4 lectures): Boolean circuits. Uniformity.
Circuit value problem, connection to standard Turing model.
The world inside P. Branching Programs, Word problems. Algebraic
Characterisation of circuit classes NC^1 (Barrington).
Power of Negations in Boolean Circuits, Markov's and Fisher's theorems.
Skipped: Algebraic Characterisation for AC^0 and ACC^0 (Barrington-Therein) - Bounds in Boolean circuits (5 lectures): Asymptotic circuit size bounds.
Shannon, Lypanov Theorems. Explicit Lower bound question.
Random Restriction Method : The Switching Lemma. Exponetialy size
lower bound for parity function against constant-depth circuits.
Razborov-Smolensky Polynomial Method: Proof that AC^0 circuits even when
allowed to use mod p gates can't compute mod q (when p and q are distinct primes).
Razborov's Clique Approximation Method: Clique is not in monotone-P.
Power of negations. An explicit function that can not be computed by poly size
circuit with log n - loglog n negations in them.
Skipped : Super logarithmic (and linear) depth lower bounds for monotone circuits computing reachability, perfect matching etc. Lower bounds for clique against loglog n negation limited circuits. communication complexity and depth of circuits. - Randomized Complexity theory (8 lectures) : Use of randomness. Classes BPP
and RP. Deranodmization goals. Expanders, Extractors and PRGs. Derandomization of space
bounded randomized algorithms, error reduction using expanders. Nisan-Wigderson generator.
Conditional derandomization results. Hardness Amplification.
Interactive Proofs, IP = PSPACE, the PCP-Theorem(statement).
Skipped : Average Case Complexity, PCP Theorem. - Arithmetic Circuits (2 lectures): Recap of counting. #P completeness of Permanent. Arithmetic circuits. Permanent vs Determinant Problem. Impagliazzo-Kabanets theorem. Algebraic Complexity Theory (basics and directions).
- Limitations of current techniques (2 lectures): Relativization (recap), Natural proofs, Algebrization. Other directions in Complexity Theory.
Coursework and Grading
Three parameters :Problem Sets: A set of problems (problem sets) will be posted (here and here) based on every 8 lectures (thats the plan!). All students who are crediting the course are required to turn in the solutions, which will be graded and returned before 2 weeks after the submission date. The grades from homeworks will be contributing towards 30% of the final grade. Here are some guidelines for working on the problem sets:
- You may turn the solutions in either handwritten or as a pdf file.
- You are encouraged to discuss among yourselves (or receive other inputs) as long as you write up your solutions by yourselves. If you indicate the (inspirational) inputs that you received while solving the problems, that will be highly appreciated.
- You may use the latex file to add your solutions to it (in this case you may need two files include.tex and preamble.sty).
- If you are using MS-word format for writing up the solutions, please do not send me the doc file directly. You can either send me a pdf file (use standard conversion procedures) or give me a printout of the doc file (Thanks !).
Scribing Notes: Each student is required to scribe three lectures; the scribed notes will count for 30% of the grade. A final project will count for 40% of the grade.