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 :

Remarque 1: Pour bien comprendre votre article vous pouvez être 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 (google scholar est un bon point de départ), et aussi sur les sites des éditeurs grâce aux abonnements de la bibliothèque.
Si malgré tout vous n'arrivez pas à trouver certains documents importants, prévenez moi, je pourrai peut-être vous aider...

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

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. Pour Anael Grandjean. Exposé le 6 décembre. Son rapport.

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. Pour Lucca Beraud Hirschi. Exposé le 6 décembre. 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.

Et des bornes inférieures pour le modèle des circuits arithmétiques :

N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 1996.

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 Vincent Despré. Exposé le 29 novembre. Son rapport.

L’article suivant donne des méthodes combinatoires pour calculer le déterminant.
M. Mahajan and V. Vinay. Determinant : old algorithms, new insights.
SIAM Journal on Discrete Mathematics, 1999.

Une caractérisation de VP :

A. Durand, F. Capelli, S. Mengel. The arithmetic complexity of tensor contractions. Pour Etienne Miquey. Exposé le 6 décembre. Son rapport.