Emploi du temps et calendrier

• 29 novembre : Tests
• 6 et 13 décembre : Tests
• 20 décembre : relâche.
• 10, 17, 24 et 31 janvier : Algorithmes approchés
• 7 février : Algorithmes approchés
• 14 et 21 février : Tests
• 28 février : présentations d'articles

• Chang Ech-chatbi - Fusy Eric :
  Self-testing without the generator bottleneck
• Sakkour Bassen - ? Georges :
  Robust characterization of polynomials
• Moro Pierre :
  The string edit distance matching problem with moves
• Camara Thomas - Hakim Walid :
  Generlized k clustering
• Malinaud Cécile - Ponty Yann :
  Approximation algorithms for grammar based compression
• Fousse Laurent - Sirvent Thomas :
  Approximate subset matching with don't cares
• Bonneau Nicolas - Barbier Johann :
  The mathematics of playing golf
• Levy Ethan :
  Max TSP
• Thai Quang - Giroire Frédéric :
  Linear-size approximate voronoi diagrams
• Riviere Romain :
  How to cut a cake

Bibliographie utile pour le cours d'Algorithmes approchés

• Page du cours de l'an dernier.
• Livre : Approximation Algorithms, de Vijay Vazirani, Springer-Verlag 2001, ISBN 3-540-65367-8.
• Notes de cours sur le web
  • Williamson.
  • Cheriyan et Ravi.

Bibliographie utile pour le cours de Tests

• Synthèses
  • M. Kiwi, F. Magniez et M. Santha. Exact and approximate testing/correcting of algebraic functions: A survey. Proc. 1st SOTACS, LNCS, volume 1770, pages 302-313, 2000.
  • F. Magniez. Auto-test pour les calculs approché et quantique. PhD thesis, Université Paris-Sud, France, 2000.
  • E. Fischer. The art of uninformed decisions: A primer to property testing. Bulletin of the EATCS, volume 75, pages 97-126, 2001.
  • M. Sudan. Probabilistic checkable proofs, course notes, 2000.
  • S. Arora. Probabilistic checking of proofs and the hardness of a pproximation problems, Ph.D. thesis, UC Berkeley, 1994.
• Articles
  • M. Blum, M. Luby et R. Rubindeld. Self-testing/correcting with applications to numerical problems. J. Comp. and Syst. Sci., volume 47(3), pages 549-595, 1993.
  • R. Rubinfeld et M. Sudan. Robust characterizations of polynomials and their applications to program testing. SIAM J. Comput., volume 25(2), pages 252-271, 1996.
  • R. Rubinfeld. On the robustness of functional equations. SIAM J. Comput., volume 28(6), pages 1972-1997, 1999.
  • F. Ergün, R. Kumar et D. Sivakumar. Self-testing without the generator bottleneck. SIAM J. Comput., volume 29(5), pages 1630-1651, 2000.
  • R. Kumar et D. Sivakumar. Efficient self-testing/self-correction of linear recurrences. Proc. FOCS, pages 602-611, 1996.
  • M. Kiwi, F. Magniez et M. Santha. Approximate testing with error relative to input size. J. Comput. System Sci., à paraître.
  • F. Magniez. Multi-linearity self-testing with relative error. Proc. 17th STACS, LNCS, volume 2292, pages 30-83, 2000.
  • O. Goldreich, S. Goldwasser et D. Ron. Property testing and its connection to learning and approximation. J. ACM, volume 45(4), pages 653-750, 1998.
  • N. Alon, E. Fischer, M. Krivelevich et M. Szegedy, Efficient testing of large graphs, Combinatorica, volume 20, pages 451-476, 2000.
  • N. Alon, M. Krivelevich, I. Newman et M. Szegedy. Regular languages are testable with a constant number of queries. SIAM J. Comput., volume 30(6), pages 1842-1862, 2000.

Stages de l'équipe Algo du LRI