Cette page est destinée à recevoir du matériel pour le cours de complexité algébrique.
On y trouve notamment la thèse de Guillaume Malod et des notes de cours de Bruno Poizat (cours1, cours2).
Pour ceux qui auraient rencontré ses notes de cours d'avril 2005: ces deux cours de 2006 les remplacent.

A lire également un article de Guillaume Malod et Natacha Portier. Il reprend en particulier (en anglais) des résultats de la thèse de Malod, dont  certains vus au début de mon cours.
A must-read if you need a reference in English.

Revenez de temps en temps pour voir s'il y a du nouveau!

Format des rapports: Merci de vous limiter à 10 pages au format 11 point (figures non comprises).
A titre d'exemple, vous pouvez consulter deux rapports rédigés par Sylvain Périfel (sur les automates cellulaires et les pavages), et un rapport rédigé par Sylvain Collange (sur l'arithmétique des ordinateurs). Notez bien qu'il s'agit simplement d'exemples de travaux réalisés par vos prédéceseurs, et pas nécessairement de modèles à suivre aveuglément pour rédiger votre propre rapport.


Sujets d'exposés:
Voici une liste d'articles à exposer. Il y en a maintenant assez pour tout le monde. Je n'en ajouterai donc probablement plus, sauf si je m'aperçois d'un oubli impardonable. Faites moi signe quand-meme si vous ne trouvez pas votre bonheur dans cette liste, je verrai ce que je peux faire.

Remarque 1: Pour bien comprendre votre article vous pouvez etre amenés à consulter d'autre documents (livres, articles...).
C'est à vous de décider de ce que vous avez besoin de lire, et de trouver les documents. De nos jours on trouve beaucoup de chose en accès libre sur le web, et aussi sur les sites des éditeurs grace aux abonnements de la bibliothèque.
Si malgré tout vous n'arrivez pas à trouver certains documents importants, prévenez moi, je pourrai peut-etre vous aider...

Remarque 2 : Les rapports sur les exposés sont à rendre au plus tard une semaine complète avant l'exposé. De préférence, envoyez moi un fichier par courrier électronique pour que je le mette sur cette page.

L.G. Valiant, S. Skyum, S. Berkowitz and C. Rackoff. Fast parallel computation of polynomials using few processors.
SIAM J. Computing, 12(4):641-644, 1983.
Comme l'article est très court il faudrait faire un travail supplémentaire :
par exemple donner les démonstrations des résultats annoncés sans démonstration, ou exposer le papier conjointement avec le papier suivant, qui porte sur le meme sujet.

G. Miller, V. Ramachandran, and E. Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits.
SIAM J. Computing, 17(4):687-695, 1988. Pour Muhammad Mumtaz Ahmad. Exposé le 1er décembre. Son rapport.
Relecteurs: Stéphane Leroux + Thibaut Balabonski.

E. Kaltofen and B. Trager. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators.  J. Symbolic Comput., 9(3):301-320, 1990.
Des algorithmes sur les polynômes dans un modèle encore plus général que les SLP: le modèle des "boîtes noires."
Pour Laurent Boyer. Exposé le 12 janvier (et non pas le 15 décembre comme prévu initialement). Son rapport.
Relecteurs: Fanny Dufossé et Thibaut Balabonski.

Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings.
J. ACM, 29(3):874-897, 1982. Des bornes inférieures exactes dans un modèle de calcul sans soustractions.
Pour Loïck Magnin. Exposé le 15 Décembre. Son rapport.
Relecteurs: Nicolas Perrin et Romain Demangeon.


R. Sengupta and H. Venkatsewaran. A lower bound for monotone arithmetic circuits computing 0-1 permanent.
Theoretical Computer Science, 209:389-398, 1998.
Encore une borne inf pour le permanent sans soustractions.
Devinette : quoi de neuf par rapport à l'article précédent ?
Pour Nicolas Perrin. Exposé le 1er Décembre. Son rapport.
Relecteurs: Loïck Magnin + Omar Fawzi.

Et maintenant, une borne inf pour le permanent dans un modèle avec soustractions!
T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem.
International Mathematics Research Notices (IMRN) 79, pages 4241--4254, 2004.
Pour Martin Delacourt. Exposé le 15 Décembre. Son rapport.
Relecteurs: Pierre Rannou et Omar Fawzi.


L. Babai and L. Fortnow. Arithmetization: a new method in structural complexity theory.
Computational Complexity 1(1):41-66, 1991.
Des SLP mais en complexité booléenne. Un article qui conviendrait à des gens ayant de bonnes connaissances dans ce domaine.
Pour Pierre Rannou. Exposé le jeudi 23 novembre. Son rapport. Relecteurs : Nicolas Perrin et Muhammad Mumtaz Ahmad.

E. Allender, P. Bürgisser and J. Kjeldgaard-Pedersen. On the complexity of numerical analysis. Proc. of 21st Ann. IEEE Conference on Computational Complexity, pp. 331-339, 2006.
Quelle est la complexité booléenne de l'évaluation du signe d'un SLP sur des entrées entières ?

P. Bürgisser.Cook's versus Valiant's Hypothesis. Theor. Comp. Sci. 235:71-88 (2000).
Relations entre complexité algébrique et complexité booléenne. Pour Omar Fawzi. Exposé le jeudi 23 novembre. Son rapport. Relecteurs : Xavier Pujol et Laurent Boyer.

P. Bürgisser. On the structure of Valiant's complexity classes.
Discr. Math. Theoret. Comp. Sci. 3:73-94 (1999).
Des versions algébriques de certains résultats classiques de complexité booléenne.

A. Barvinok. Two algorithmic results for the traveling salesman problem.
Mathematics of Operations Research, 21:65-84, 1996.
Montre que le permanent et le polynome qui énumère les circuits hamiltoniens peuvent s'évaluer en un nombre polynomial d'opérations si on se restreint à des matrices de rang borné. Pour Fanny Dufossé. Exposé le 12 janvier. Son rapport.
Relecteurs: Xavier Pujol, Laurent Boyer, et Muhammad Mumtaz Ahmad.

B. Courcelle, J. A. Makowsky, and U. Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics, 108:23-52, 2001.
Cet article donne une autre restriction permettant d'évaluer efficacement des polynomes difficiles tels que le permanent.
Pour les amateurs de logique.
Pour Thibaut Balabonski. Exposé le jeudi 23 novembre. Son rapport. Relecteurs : Fanny Dufossé et Romain Demangeon.

J. A. Makowsky and K. Meer. Polynomials of bounded treewidth. Foundations of Computational Mathematics, Proceedings of the Smalefest 2000, Felipe Cucker and J. Maurice Rojas, edts., World Scientific 2002, pp. 211-250.
Dans le meme ordre d'idées que le précédent, mais le point de vue "complexité algébrique" est plus développé.


M. Mahajan, P. R. Subramanya and V. Vinay. The combinatorial approach yields an NC algorithm for computing Pfaffians.
Discrete Applied Mathematics, 143:1-16, 2004.
Montre entre autre chose que si on se restreint aux graphes planaires, le calcul du permanent (où si on préfère du nombre de couplages parfaits) devient facile. Cet article pour Romain Demangeon. Exposé le 1er décembre. Son rapport. Relecteurs: Martin Delacourt+ Fanny Dufossé.

H. B. Hunt, III, M. V. Marathe, V. Radhakrishnan and R. E. Stearns. The complexity of planar counting problems. SIAM Journal on Computing, 27(4):1142-1167, 1998. Un bon complément à l'article précédent : montre que meme si on se restreint à des graphes planaires, de nombreux problèmes restent difficiles. Que de la complexité booléenne.
Cet article pour Xavier Pujol. Exposé le 12 janvier. Son rapport. Relecteurs: Pierre Rannou + Loïc Magnin.