Computer Science
Tel-Aviv University

Computational Complexity Theory

0368.4105.01

Spring 2012

Lectures

Tuesday 10:00-13:00, Melamed 006
Instructor

Amnon Ta-Shma | Schreiber 127 | 6405364
T.A

Jenny Falkovich | Handasat Tochna 209

Requirements


Prerequisites


Announcements


Final Exam


Midterm


Homework assignments

  • Submit Homeworks to the wooden box titled "Complexity" near Shreiber 004-005.
  • Collect graded homeworks from the copy room.
  • To appeal, write your arguments and submit it together with the original homework, same as you submit homeworks.
  • Answered appeals can be collected from the copy room as well.
  • Final grades for HomeWorks are here

  • Some Information

    Textbooks

    Main references:
    [AB] Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak
    [S] Introduction to the Theory of Computation, by Michael Sipser (1st or 2nd edition only)
    [P] Computational Complexity, by Christos H. Papadimitriou
    Other textbooks:
    [MOV] Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone.
    [MR] Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan
    [V] Approximation Algorithms, by Vijay V. Vazirani
    [CLR] Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
    Previous Exams
    Previous exams
    Other links
    A compendium of NP-complete problems and what's known about them.
    A compendium of problems in higher levels of the hierarchy, part I and part II.
    The zoo of all(?) known complexity classes.

    Schedule

    Date Class Topic Notes Date Recitation Topic Notes
    Mar 6
  • Administration;
  • Turing machine model of computation [AB 1];
  • Time hierarchy theorem [AB 3.1];
  • Oracle machines [AB 3.5].
  • Circuits [AB 6.1]
  • Lecture 1
  • Mar 6

    Strike

  • Complexity Functions
  • Turing Machines
  • Recitaion 1
  • Mar 13
  • Space complexity [AB 4, S 8];
  • L, PSPACE.
  • stCON is space(log^2n) [AB 4.2.1];
  • Logspace Reductions, Composition in L [AB 4, S 8.1];
  • CVAL is P-complete under log-space reductions [6.7.2]
  • Lecture 2
  • Mar 13

    Strike

  • Simulating Muli-tape Turing machine by a single tape Turing machine with quadratic time overhead.
  • Recitaion 2
  • Mar 20
  • TQBF is PSPACE-complete [AB 4.3];
  • NP [AB 2.5];
  • CSAT and 3SAT are NP-complete [S 7.4];
  • Lecture 3
  • Mar 20
  • Boolean Circuits
  • Oracle Machines
  • Recitaion 3
  • Mar 27
  • 3NAE, 3COL, Clique, IS, VC and Setcover are NPC.
  • coNP.
  • NSpace.NL. [AB 4.3, S 8.1];
  • STCON is in NL. [AB 4.4];
  • STCON is in coNL.
  • Lecture 4
  • Mar 27
  • Equivallence of 2 definitions of NP;
  • Karp Reduction;
  • Question on unary NPC language.
  • Recitaion 4
  • Apr 3
  • Zero-error NL,
  • NL=coNL.
  • The polynomial time hierarchy.
  • Pratt certificates for primality (See...)
  • Defined RP, BPP
  • Lecture 5
  • Apr 3
  • Separation with Diagonalization
  • Padding Argument
  • Recitaion 5
  • Apr 17
  • Amplification of BPP algorithms, Chernoff bound.
  • Schwartz-zippel lemma. (See...)
  • A probabilistic algorithm for Matching in a bi-partite graph.
  • Polynomial identity testing.
  • Lecture 6
  • Apr 17
  • The polynomial time hierarchy.
  • Recitaion 6
  • Apr 24
  • Karger's min-cut algorithm - primality testing with a probabilistic algorithm (Fermat, Euler, Rabin-Miller (no proof)).
  • Lecture 7
  • Apr 24
  • 2 Definitions of NL.
  • 2SAT is in NL.
  • Recitaion 7
  • May 1
  • Communication complexity.
  • The log-rank lower bound.
  • An exponential gap between the deterministic and probabilistic communication complexity of the EQ function.
  • Schoning's algorithm for 3SAT.
  • Lecture 8
  • May 1
  • Small Examples
  • Recitaion 8
  • May 8
  • Quiz
  • The Karp-Lipton theorem.
  • Lecture 9
  • May 8
  • Self Reducibility
  • Search vs Decision
  • Griddy Derandomization Algorithm.
  • Recitaion 9
  • May 15
  • BPP in Sigma_2
  • Approximation algorithms.
  • 2-approximation for VC, ln(n) approximation for SetCover.
  • Every graph has a cut with at least |E|/2 edges.
  • Pairwise independent distributions (def+construction).
  • A deterministic algorithm for a large cut by de-randomizing the probabilistic proof.
  • Lecture 10
  • May 15
  • Amplifications of BPP.
  • If SAT is in BPP then SAT is in RP.
  • Recitaion 10
  • May 22
  • Public coins, MA, AM, IP.
  • GNISO is in AM.
  • MA in AM,
  • if GISO is NP-complete the hierarchy collapses.
  • AM in Pi_2.
  • IP in PSPACE.
  • Lecture 11
  • May 22
  • #SAT is #P-Complete.
  • Recitaion 11
  • May 29
  • #3SAT in IP. [AB 8.3]
  • Sketch of PSPACE=IP. [P 19.2]
  • If PSPACE has polynomial size circuits then PSPACE=MA.[AB 8.4]
  • Defined PCP(r(n),q(n)).[AB DEF. 11.4]
  • Lecture 12
  • May 29
  • Approximating TSP
  • Recitaion 12
  • Jun 5
  • The PCP theorem.
  • The PCP theorem implies Gap Max3SAT is NP-hard.
  • Hardness of approximation.
  • Gap preserving reductions.
  • Max-clique is NP-hard to approximate up to some constant.
  • An amplified PCP theorem.
  • Max-clique is NP-hard to approximate up to n^alpha for some constant alpha.
  • Lecture 13
  • Jun 5
  • PCP
  • Recitaion 13
  • Jun 12
  • Hardness of approximating VC.
  • The importance of the gap location.
  • Gp max 3SAT(b) (using expanders).
  • Error correcting codes and the Hadamard code.
  • Lecture 14
  • Jun 12
  • SubsetSum is NPC but Gap-SubsetSum[1-e,1] is easy for any e<1.
  • Recitaion 14
  • Jun 19
  • NOT FOR EXAM.
  • 2-Local decoding of the Hadamard code.
  • Linearity testing of the Hadamard code (with analysis using Fourier transform).
  • QuadEQ is NP-complete. QuadEq in PCP(poly(n),O(1)).
  • Lecture 15 NOT FOR EXAM
  • Jun 19
  • Examples
  • Recitaion 15