Articles

Nonnegative rank measures and algebraic branching programs [pdf]
Hervé Fournier, Guillaume Malod, Maud Szusterman and Sébastien Tavenas. In Proc. FSTTCS, pp 15:1-15:14, 2019.
Report ECCC TR19-100.

The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials [pdf]
Hervé Fournier, Nutan Limaye, Meena Mahajan and Srikanth Srinivasan. Theory of Computing, 13(9): 1-34, 2017.
Preliminary version: In Proc. MFCS, pp 324-335, 2015.

Computing the Gromov hyperbolicity of a discrete metric space [pdf]
Hervé Fournier, Anas Ismail and Antoine Vigneron. Information Processing Letters, 115(6-8): 576-579, 2015.

Lower bounds for depth 4 formulas computing iterated matrix multiplication [pdf]
Hervé Fournier, Nutan Limaye, Guillaume Malod and Srikanth Srinivasan. SIAM Journal on Computing, 1173-1201, 2015.
Preliminary version: In Proc. STOC, pp 28-135, 2014.

On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant [pdf]
Hervé Fournier, Sylvain Perifel and Rémi de Verclos. Information and Computation, 240:31-41, 2015.
Preliminary version: In Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 433-444, 2013.

A deterministic algorithm for fitting a step function to a weighted point-set [pdf]
Hervé Fournier and Antoine Vigneron. Information Processing Letters, 113(3):51-54, 2013.

Monomials in arithmetic circuits: Complete problems in the counting hierarchy [pdf]
Hervé Fournier, Guillaume Malod and Stefan Mengel. Computational Complexity, 24(1): 1-30, 2015.
Preliminary version: In Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp 362-373, 2012.

The fraction of large random trees representing a given Boolean function in implicational logic [pdf]
Hervé Fournier, Danièle Gardy, Antoine Genitrini and Bernhard Gittenberger. Random Structures and Algorithms, 40(3): 317-349, 2012.
Preliminary version: Complexity and limiting ratio of boolean functions over implication. In Proc. 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 5162 of LNCS, pp 347-362, 2008.

Fitting a step function to a point set [pdf]
Hervé Fournier and Antoine Vigneron. Algorithmica, 60(1):95-109, 2011.
Preliminary version: In Proc. 16h European Symposium on Algorithms (ESA), volume 5193 of LNCS, pp 442-453, 2008.

Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns [pdf]
Hervé Fournier and Olivier Teytaud. Algorithmica, 59(3):387-408, 2011.
Preliminary version: Lower bounds for evolution strategies using VC-dimension. In Proc. 10th International Conference on Parallel Problem Solving from Nature (PPSN), volume 5199 of LNCS, pp 102-111, 2008.

Tautologies over implication with negative literals [pdf]
Hervé Fournier, Danièle Gardy, Antoine Genitrini and Marek Zaionc. Mathematical Logic Quarterly, 56(4):388-396, 2010.

On the shape of decomposable trees [pdf]
Dominique Barth, Hervé Fournier and Romain Ravaux. Discrete Mathematics, 309: 3882-3887, 2009.

Balanced And/Or trees and linear threshold functions [pdf]
Hervé Fournier, Danièle Gardy and Antoine Genitrini. In Proc. 6th SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp 51-57, 2009.

On the construction of a family of transversal subspaces over finite fields [pdf]
Alexander Chistov, Hervé Fournier, Pascal Koiran and Sylvain Perifel. Linear Algebra and its Applications, 429(2-3):589-600, 2008.

Universal relations and #P-completeness [pdf]
Hervé Fournier and Guillaume Malod. Theoretical Computer Science, 407:97-109, 2008.
Preliminary version: In Proc. 6th Conference on Algorithms and Complexity (CIAC), volume 3998 of LNCS, pp 368-379, 2006.

A tight lower bound for computing the diameter of a 3D convex polytope [pdf]
Hervé Fournier and Antoine Vigneron. Algorithmica, 49(3):245-257, 2007.
Preliminary version: Lower bounds for geometric diameter problems. In Proc. 7th Latin American Theoretical Informatics Symposium (LATIN), volume 3887 of LNCS, pp 467-478, 2006.

Classical and intuitionistic logic are asymptotically identical [pdf]
Hervé Fournier, Danièle Gardy, Antoine Genitrini and Marek Zaionc. In Proc. 16th EACSL Annual Conference on Computer Science and Logic (CSL), volume 4646 of LNCS, pp 177-193, 2007.

A degree bound on decomposable trees [pdf]
Dominique Barth and Hervé Fournier. Discrete Mathematics, 306(5): 469-477, 2006.

Vandermonde Matrices, NP-completeness and transversal subspaces [ps] [pdf]
Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran. Foundations of Computational Mathematics, 3(4):421-427, 2003.

Quantifier rank for parity of embedded finite models [ps] [pdf]
Hervé Fournier. Theoretical Computer Science, 295(1-3):153-169, 2003.
Preliminary version: In Proc. 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 2136 of LNCS, pp. 375-386. Springer, 2001.

Sparse NP-complete problems over the reals with addition [ps] [pdf]
Hervé Fournier. Theoretical Computer Science, 255(1-2):607-610, 2001.

Lower bounds are not easier over the reals: inside PH [ps] [pdf]
Hervé Fournier and Pascal Koiran. In Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP), volume 1853 of LNCS, pp. 832-843, 2000.

Are lower bounds easier over the reals? [ps] [pdf]
Hervé Fournier and Pascal Koiran. In Proc. 30th ACM Symposium on Theory of Computing (STOC), pp. 507-513, 1998.

Autre

Complexité du calcul de polynômes et de problèmes géométriques [pdf]
Mémoire d'HdR, Université Paris Diderot, 2014.

Complexité et expressibilité sur les réels [pdf]
Mémoire de thèse de doctorat, ENS Lyon, 2001.