Cette page est destinée à recevoir du matériel pour le cours de complexité algébrique.
On y trouve notamment des références sur les circuits arithmétiques : la thèse de Guillaume Malod et des notes de cours de Bruno Poizat (cours1, cours2).

A lire également un article de Guillaume Malod et Natacha Portier.

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 (liste en construction) :

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.

Articles sur le modèle BSS :

L. Blum, F. Cucker, M. Shub, S. Smale. Algebraic settings for the problem « P ≠ NP ». The mathematics of numerical analysis (1995 AMS-SIAM seminar in applied mathematics). Il faudrait exposer principalement les aspects non vus en cours, notamment la section 3. Pour les amateurs de theorie des nombres. Exposé de Hugo Labrande le 24 novembre. Son rapport.

M. Prunescu. Structure with fast elimination of quantifiers. The Journal of Symbolic Logic, 71(1) : 321-328, 2006. Construction d’une structure où P=NP. Pour les amateurs de logique. Exposé de Martin Bodin le 1er décembre. Son rapport.

Articles sur les circuits arithmétiques (modèle de Valiant, deuxième partie du cours) :

D’abord deux articles sur la parallélisation des circuits arithmétiques.

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.

R. Raz and A. Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008.

P. Hrubes, A. Wigderson, A. Yehudayoff, Relationless completeness and separations  Proceedings of IEEE Computational Complexity Conference 2010, pp. 280-290. ECCC Report TR10-040, 2010
http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/HWY10_rel/HWY10_rel_proc.pdf. Exposé de Florent Capelli le 24 novembre. Son rapport.

Et maintenant, une borne inférieure pour la représentation du permanent comme déterminant.
T. Mignon and N. Ressayre. A quadratic bound for the determinant and permanent problem.
International Mathematics Research Notices (IMRN) 79, pages 4241--4254, 2004.

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é. Exposé de Guillaume Vors le 1er décembre. Son rapport.


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.