Master MPRI/M2R
Course 2-11-2, 2005/06
Game theory: proofs, testing and equilibria
Organization
Place: 30 rue du Chateau des Rentiers, room 131, first floor
Time: Friday, 12h45-15h45
- Probabilistic verification (12h, Frédéric Magniez)
- 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
- 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
- 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)
- 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.