Organization

• Probabilistic verification (12h, Frédéric Magniez)
  1. 09/12: Interactive Proofs
     In part based on Muli Safra's slides and Sections 16.1 & 16.2 of the book Logic and Complexity (see References)
     • Motivations, definition of verifier, prover, and class IP
     • Graph Non Isomorphism in IP
     • IP in PSPACE
     • Arithmetisation of boolean formulas
     • #P included in IP: arithmetisation of boolean formulas, #SAT in IP
     • PSPACE included in IP: QBF in IP
  2. 16/12: Probabilistic Checkable Proofs, Linearity Testing
     In part based on Lecture 3 of Madhu Sudan's lectures on PCP, Sections 16.3 & 16.4 of the book Logic and Complexity (see References) and Sections 2.1, 2.2 & 2.3 of F.M.'s survey for the Linearity testing part
     • Motivation, definition of a PCP verifier and class PCP(r(n),q(n))
     • Simple relations with classes NP and MIP(=NEXP)
     • The main Theorem (PCP(O(log n),O(1))=NP): structure of the proof, consequences of the theorem
     • Proof of one step (NP included in PCP(poly(n),O(1))): Hadamard code, Linearity self-tester/corrector
  3. 06/01: Testing of Graph Properties
     In part based on Sections 2.1 & 2.3 of a tutorial by Dana Ron
     • Motivations, definition of a property testers, simple examples
     • Context of dense graphs: adjency model, distance on graphs
     • Bipartiteness Tester: lower bound, intermediate case (with given coloring), full tester
     • Discussion on k-colorability (k>2)
  4. 13/01: Testing of Regular Properties
     In part based on Section 4.2 of the above tutorial, a F.M.'s work, and (maybe) another recent F.M.'s work
     • Definition of the edit distance
     • (essentially) Strongly connected automata, languages without given patterns
     • General case when the distance allows block moves
     • Discussion on approximating the edit distance (with moves)
  
  
• 13/01: Homework (updated version) to give back for 10/02 (extended deadline)
  Typo 1 (thanks to Jean Philippe Aumasson): In Property Testing for Sorting, correct the while-loop condition of Inceasing Test to "While b != a+1" (replaced by Typo 7)
  Typo 2 (thanks to Jean Philippe Aumasson): In Property Testing of Languages..., add a stop condition for the inductive algorithm Language Test "If |S|=1 then apply tester of Question 14"
  Typo 3 (thanks to Jean Philippe Aumasson): In Probabilistic Checkable Proofs, the polynomials in QP-SAT are quadratic as in the lecture
  Typo 4 (thanks to Jean Philippe Aumasson): In Probabilistic Checkable Proofs, Question 3, the tester uses O(m) random bits, and in Question 8, replace n by the input size of the instance of QPSAT.
  Typo 5 (thanks to Clément Houtmann): In Property Testing for Sorting, correct the second if-condition of Inceasing Test to "If (T[a] < T[i] and T[b] != T[i]) or (T[b] > T[i] and T[a] != T[i])" (replaced by Typo 8)
  Typo 6 (thanks to Clément Houtmann): In Property Testing for Sorting, in the definition of good replace x_i by T[i]
  Typo 7: In Property Testing for Sorting, correct the while-loop condition of Inceasing Test to "While b>a+1"
  Typo 8 (thanks to Clément Houtmann): correct the second if-condition of Inceasing Test to "If (T[a] != T[i] and T[b] != T[i]) or (T[a] > T[b])
  
  
• Algorithmic of games (12h, Michel de Rougemont)
  
  
• 17/02 or 24/02: Examination

References

• Logic and Complexity. R. Lassaigne et M. de Rougemont. Springer-Verlag, 2003..
• Computational Complexity. C. H. Papadimitriou. Addison Wesley, 1994.
• Randomized Algorithms. R. Motwani et P. Raghavan. Cambridge University Press, 1995.
• The art of uninformed decisions: A primer to property testing. E. Fischer. Bulletin of the EATCS, volume 75, pages 97--126, 2001.
• Exact and approximate testing/correcting of algebraic functions: A survey. M. Kiwi, F. Magniez, and M. Santha. Theoretical Aspects of Computer Science, LNCS 2292, pages 30-83, 2002.
• A course in game theory. M. J. Osborne et A. Rubinstein. MIT Press, 1994.