18.405 – Advanced Complexity with Prof. Madhu Sudan

(Return to Petar Maymounkov's homepage.)

Related links:

Problem Sets:

Syllabus

  • 2/12/04:
    Diagonalization
    Relativization, Baker-Gill-Solovay Theorem: There are $A$ and $B$ such that $\\mathrm{P}^A=\\mathrm{NP}^A$ and $\\mathrm{P}^B \\neq \\mathrm{NP}^B$
    Ladner's Theorem: Between any two languages (one not polynomially reducible to the other) there exist incomparable languages
  • 2/20/07:
    Neciporuk's Theorem: An explicit function having a super-linear lower-bound on formula size
    Barrington's construction of small-width Branching Programs
  • 2/21/07:
    Furst-Saxe-Sipser: Parity is not in $\\mathrm{AC}^0$, Switching Lemma and Random Restrictions
  • 2/26/07:
    Razborov, Method of Approximations: Replacing deterministic gates with probabilistic polynomials
    Simplicity of $\\mathrm{AC}^0$ Lemma by Smolensky: Circuits in $\\mathrm{AC}^0$ can be approximated by low-degree polynomials on large fraction of inputs
    DeMillo-Lipton-Schwartz-Zippel Lemma of Computer Science
    Parity cannot be approximated by low-degree polynomials
  • 2/28/07:
    Communication complexity (CC)
    Karchmer-Wigderson games: Communication Complexity = Circuit depth of function
    Tiling Complexity (Yao), Tiling Lemma: Lower-bound on CC
    The rank lower bound on CC (Mehlhorn and Schmidt, STOC'82)
  • 3/5/07:
    Alternation I: Alternating Machines, Space/Time/Alternation equivalences
    OPEN: Can you solve directed ST-connectivity in $O(\\log^{2-\\epsilon} n)$ space for $\\epsilon > 0$?
    OPEN: Does $\\mathrm{NSPACE}(s) \\subseteq \\mathrm{SPACE}(s^{2-\\epsilon})$ for $\\epsilon > 0$?
    Fortnow's Theorem
  • 3/7/07:
    Alternation II: The Polynomial Hierarchy, classes $\\Sigma^{\\mathrm{P}}_i$ and $\\Pi^{\\mathrm{P}}_i$
    Karp-Lipton Theorem
  • 3/12/07:
    OPEN: How to generate a prime number in $[N,2N]$ deterministically?
    OPEN: Finding square roots modulo prime deterministically (we know in RP,ZPP)
    Algebraic Circuit Identity Testing (ACIT)
    Strong Turing-Church Hypothesis
    ZPP/RP/co-RP/BPP, $\\mathrm{ZPP}=\\mathrm{RP} \\cap \\text{co-RP}$
    Amplification for (co-)RP/BPP: Success probability $1/\\mathrm{poly}(n)$ is equivalent to success probability $1-1/2^{\\mathrm{poly}(n)}$
  • 3/14/07:
    Amplification: Strong BPP = Weak BPP
    [Adleman] $\\mathrm{BPP} \\subseteq \\mathrm{P/poly}$. Implies: $\\mathrm{NP} \\subseteq \\mathrm{BPP} \\Rightarrow \\mathrm{NP} \\subseteq \\mathrm{P/poly} \\subseteq$ Polynomial Hierarchy collapses
    [Sipser, Lautemann] $\\mathrm{BPP} \\subseteq \\Sigma_2$
    One-way permutations
    [Valiant-Vazirani] $\\mathrm{SAT} \\leq_{\\mathrm{RP}} \\text{UNIQUE-SAT}$: Part I
  • 3/19/07:
    $\\mathrm{SAT} \\leq_{\\mathrm{RP}} \\mathrm{UNIQUE-SAT}$
    OPEN: Can we derandomize?
    OPEN: Can we even just improve the probability of success in the reduction?
    $\\mathrm{SAT} \\leq_{\\mathrm{STRONG-BP}} \\oplus \\mathrm{SAT}$
    $\\mathrm{NP} \\leq \\oplus \\mathrm{SAT}$
    [Toda] Parity/BP/existential/for-all operators
    $\\mathrm{NP} \\subseteq \\mathrm{BP} \\cdot \\oplus \\cdot \\mathrm{P}$ and $\\text{co-NP} \\subseteq \\mathrm{BP} \\cdot \\oplus \\cdot \\mathrm{P}$
  • 3/21/07:
    $\\forall,\\exists,\\oplus,\\mathrm{BP}$-operators
    Classes $\\oplus\\,C$ and $\\mathrm{BP}\\,C$ closed under complementation
    $\\oplus\\oplus\\,C \\equiv \\oplus\\,C$ and $\\mathrm{BP}\\,\\mathrm{BP}\\,C \\equiv \\mathrm{BP}\\,C$ and $\\mathrm{BP}\\,\\oplus\\,C\\equiv \\oplus\\,\\mathrm{BP}\\,C$
    Toda's Theorem: $\\Sigma_k^{\\mathrm{P}},\\Pi_k^{\\mathrm{P}} \\subseteq\\mathrm{BP}\\oplus\\,\\mathrm{P}$ and $\\mathrm{BP}\\,\\oplus\\,\\mathrm{P} \\subseteq \\mathrm{P}^{\\#\\mathrm{P}}$
  • 4/2/07:
    Interactive proofs
    [Babai-Moran] Arthur-Merlin Proofs
    [Goldreich-Micali-Wigderson] GRAPH NON-ISOMORPHISM by IP[2]
    Private coins = public coins
    One-sided error = two-sided error
    $\\text{NP}\\subseteq \\text{MA}$ and $\\text{MA}\\subseteq \\text{AM}$ and $\\text{BPP}\\subseteq \\text{MA}=\\text{AMAMAM ... } \\subseteq \\text{IP}[\\text{poly}]= \\text{PSPACE}$. Last equality by [Lund-Fortnow-Karloff-Nissan, Shamir]
  • Private coins and 2-sided error = public coins and 1-sided error
    PERMANENT is random-self reducible