Research

Publications

Note: the links below are to research reports on a web archive and correspond to long versions of the papers.

With Guillaume Lagarde.
Lempel-Ziv: a "one-bit catastrophe" but not a tragedy
ACM-SIAM Symposium on Discrete Algorithms (SODA'18), 2018.
With Hervé Fournier and Rémi de Verclos.
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
Mathematical Foundations of Computer Science (MFCS 2013), volume 8087 of LNCS, pages 433-444, 2013.
Journal version: Information and Computation, Special Issue for MFCS 2013 (K. Chatterjee and J. Sgall), 2014.

With Zeev Dvir, Guillaume Malod and Amir Yehudayoff.
Separating multilinear branching programs and formulas
Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012), pages 615-624.

With Pascal Koiran.
Interpolation in Valiant's theory
In Computational Complexity, volume 20, number 1, pages 1-20, 2011.

With Elvira Mayordomo and Philippe Moser.
Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable
In Theory of Computing Systems, volume 48, pages 731-766, 2011. (Journal version of the STACS 2008 paper)

With Pascal Koiran.
A superpolynomial lower bound on the size of uniform non-constant-depth threshold circuits for the permanent
IEEE Conference on Computational Complexity, pages 35-40, 2009.

With Alexander Chistov, Hervé Fournier, Pascal Koiran.
On the construction of a family of transversal subspaces over finite fields
In Linear Algebra and its Applications, volume 429(2-3), pages 589-600, 2008.

With Pierre Charbit, Emmanuel Jeandel, Pascal Koiran and Stéphan Thomassé.
Finding a vector orthogonal to roughly half a collection of vectors
In Journal of complexity, volume 24(1), pages 39-53, 2008.

With Pilar Albert, Elvira Mayordomo, Philippe Moser.
Pushdown compression
Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science (STACS 2008), pages 39-48, 2008.

With Pascal Koiran.
The complexity of two problems on arithmetic circuits
In Theoretical Computer Science, volume 389, pages 172-181, 2007.

With Pascal Koiran.
VPSPACE and a transfer theorem over the complex field
Mathematical Foundations of Computer Science (MFCS 2007), volume 4708 of LNCS, pages 359-370, 2007.
Journal version: Theoretical Computer Science volume 410, number 50, pages 5244-5251, 2009.

Symmetry of information and nonuniform lower bounds
Computer Science in Russia (CSR 2007), volume 4649 of LNCS, pages 315-327, 2007.

With Pascal Koiran.
VPSPACE and a transfer theorem over the reals
Symposium on Theoretical Aspects of Computer Science (STACS 2007), volume 4393 of LNCS, pages 417-428, 2007.
Journal version: Computational Complexity, volume 18, number 4, pages 551-575, 2009.

With Pascal Koiran.
Valiant's model: from exponential sums to exponential products
Mathematical Foundations of Computer Science (MFCS 2006), volume 4162 of LNCS, pages 596-607, 2006.

Thèse soutenue le 6 décembre 2007 à l'ENS Lyon, encadrée par Pascal Koiran.
Manuscrit de thèse en pdf.
Transparents de soutenance en pdf.

Talk at ENS Lyon, July 4, 2012 (in English). Separating multilinear branching programs and formulas. Available in pdf.

Talk at Dagstuhl, January 10, 2012 (in English). Exponential time vs probabilistic polynomial time. Available in pdf.

Talk at FoCM (Budapest), July 6, 2011 (in English). Lower bounds for "explicit" and "non-explicit" polynomials. Available in pdf.

Exposé à l'Institut Gaspard Monge (Marne-la-Vallée), 23 novembre 2010 (in French). Quelle est la puissance des algorithmes probabilistes polynomiaux ? En pdf.

Exposé à la fête de la science (université Paris 7), 22 octobre 2010 (in French). Quels problèmes peut-on résoudre efficacement ? En pdf (1,8 Mo).

Exposé aux journées nationales d'informatique mathématiques (GDR-IM), 21 janvier 2010 (in English). Lower bounds in Boolean and algebraic complexity. En pdf.

Exposé à la fête de la science (université Paris 7), 20 novembre 2009 (in French). Cryptographie : de l'Antiquité à nos jours. En pdf (8 Mo).

Séminaire de rentrée de l'équipe Automates (LIAFA, université Paris 7), 17 octobre 2008 (in French). Bornes inférieures non uniformes. En pdf.

Talk at LIAFA (university Paris 7), May 30, 2008. Pushdown compression. Available in pdf.

Séminaire de théorie des modèles de l'institut Camille Jordan (université Claude Bernard de Lyon), 17 janvier 2008 (in French). Interpolation en théorie de Valiant. En pdf. (English version available below)

Talk at the university of Paderborn (Germany), October 30, 2007. Interpolation in Valiant's theory. Available in pdf.

Talk for CSR 2007 in Ekaterinburg (Russia), September 4, 2007. Symmetry of information and nonuniform lower bounds. Available in pdf (more complete version available below).

Talk for MFCS 2007 in Cesky Krumlov (Czech Republic), August 30, 2007. VPSPACE and a transfer theorem over the complex field. Algebraic versions of the question "P = PSPACE?". Available in pdf.

Talk for the seminar of group Algo of LRI (Orsay), June 7, 2007. Symmetry of information and nonuniform lower bounds. Available in pdf.

Groupe de travail "Algorithmique et combinatoire" du LIAFA (Paris), 27 février 2007 (in French). Versions algébriques de la question "P = PSPACE ?" et Un vecteur orthogonal à environ la moitié d'une famille de vecteurs. En pdf.

Talk for STACS 2007 in Aachen (Germany), February 27, 2007. VPSPACE and a transfer theorem over the reals. Algebraic versions of the question "P = PSPACE?". Available in pdf.

Exposé à Montpellier pour les journées arithmétiques du GDRIM, 24 janvier 2007 (in French). La question "P=PSPACE?" dans les modèles BSS et de Valiant. En pdf.

Talk for MFCS 2006 in Stará Lesná (Slovakia), August 31, 2006. Valiant's model: from exponential sums to exponential products. Available in pdf.

Exposé à Nancy, 24 mars 2005 (in French). Un résultat de transfert entre modèles de Valiant et BSS. En dvi, ps.

Rapport de DEA, 30 juin 2004 (Lyon, sous la direction de Pascal Koiran). Polynômes donnés par des circuits algébriques et généralisation du modèle de Valiant. En dvi, ps.

Internship report (Cambridge, supervised by Anuj Dawar), August 2003. Number of variables and expressive power of first-order logic on finite ordered structures. Available in dvi, ps.

Rapport de stage (Orsay, sous la direction de Frédéric Magniez), août 2002. Autour de la transformée de Fourier quantique. En ps.