QLog (Quantized Log)

Théorie de la Complexité

Classé dans : Informatique — Sebastiao Correia 30 octobre 2006 @ 23:30
Imprimer ce billet Imprimer ce billet

Un livre en ligne sur la théorie de la complexité :

Complexity Theory: A Modern Approach / Sanjeev Arora and Boaz Barak

avec un chapitre sur le calcul quantique.
Voici la table des matières :

Part I: Basic Complexity Classes

  1. The computational model – and why it doesn’t matter. Definition of Turing machine, efficient universal TM, the class P.
  2. NP and NP completeness. NP, Cook-Levin Theorem, NP-completeness, search vs. decision.
  3. Space Complexity PSPACE, L, NL. TQBF is PSPACE complete, Savitch’s Theorem, Path is NL-complete, NL=coNL.
  4. Diagonalization Time, Non-deterministic time, and space hierarchy theorems, Ladner’s theorem, oracle machines and proof that relativized methods can’t resolve P vs. NP.
  5. The polynomial hierarchy and alternations. Definitions of PH via alternating quantifiers and alternating machines, conjecture it doesn’t collapse, time-space tradeoffs for SAT.
  6. Circuits. Boolean circuits and the class Ppoly. Definition using advice. Karp-Lipton theorem. Non-uniform hierarchy theorem. circuit-satisfiability and alternative proof for Cook-Levin theorem.
  7. Randomized Computation BPP, RP, coRP, ZPP. Examples of probabilistic algorithms. Error reduction via repetition. BPP in P/poly and PH. Randomized reductions, randomized logspace algorithms.
  8. Complexity of Counting #P. #P-completeness and Valiant’s theorem. Toda’s theorem.
  9. Interactive Proofs IP, AM. Graph non-isormorphism in AM. IP=PSPACE.
  10. Cryptography One-way functions, pseudorandom generators: prediction vs. distinguishing. Goldreich-Levin theorem. Zero knowledge and ZK proof for graph isomorphism. Overview of advanced topics in cryptography.

Part II: Lower bounds for concrete computational models

  1. Decision Trees certificate complexity, randomized complexity, sorting lowerbounds
  2. Communication Complexity Lowerbound methods (fooling set, rank, tiling, discrepancy), multiparty communication complexity
  3. Circuit lowerbounds. Hastad switching lemma, lowerbounds for monotone circuits, frontier of circuit lowerbounds, approaches using communication complexity.
  4. Algebraic complexity Algebraic trees and circuits, Blum-Shub-Smale model.

Part III: Advanced Topics

  1. Average Case Complexity: Levin’s Theory DistNP and its complete problems.
  2. Random and pseudorandom walks on graphs second eigenvalue and analysis of random walks, expander graphs, zig-zag construction of expanders, reingold’s deterministic logspace algorithm for undirected connectivity.
  3. Derandomization and Extractors Pseudorandom generators from average-case hardness – the NW generators. Extractors from hash functions. Trevisan’s extractor from NW.
  4. Hardness amplification and error correcting codes Worst-case to average case reduction. Error correcting codes. Pseudoarndom generators from worst-case assumptions. List decoding and its use for hardness amplification.
  5. PCP and hardness of approximation. NP in PCP(poly,1). The PCP theorem (Dinur’s proof). Independent set is hard to approximate within a polynomial factor.
  6. More PCP Theorems and the Fourier Transform Technique Fourier transforms over GF(2)^n. Analysis of linearity testing. Hastad’s 3-query PCP, 3SAT is hard to 7/8+epsilon approximate. Learning fourier coefficients (Goldreich-Levin / Kushilevits-Mansour)
  7. Quantum Computation Quantum computation and the class QBP. Shor’s factoring algorithm.
  8. Logic in complexity theory Proof complexity.
  9. Why are circuit lower bounds so difficult? Natural proofs.