Complexity and Limiting Ratio of Boolean Functions over Implication ⋆ (2009)
Hervé Fournier, Danièle Gardy, Antoine Genitrini, Bernhard Gittenberger
Abstract. We consider the logical system of boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely,...
UNIVERSAL RELATIONS AND #P-COMPLETENESS (2008)
Hervé Fournier, Guillaume Malod
Abstract. This paper follows the methodology introduced by Agrawal and Biswas in [AB92], based on a notion of universality for the relations associated with NP-complete problems. The purpose was to...
Lower bounds for evolution strategies using VC-dimension (2008)
Teytaud, Olivier, Fournier, Hervé
We derive lower bounds for comparison-based or selection-based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. We...
Lower bounds for evolution strategies using VC-dimension (2008)
Teytaud, Olivier, Fournier, Hervé
We derive lower bounds for comparison-based or selection-based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. We...
On the construction of a family of transversal subspaces over finite fields (2007)
Chistov, Alexander, Fournier, Hervé, Koiran, Pascal, Perifel, Sylvain
Let k be a field. We are interested in the families of r-dimensional subspaces of kn with the following transversality property: any linear subspace of kn of dimension n-r is transversal to at least...
On the construction of a family of transversal subspaces over finite fields (2007)
Chistov, Alexander, Fournier, Hervé, Koiran, Pascal, Perifel, Sylvain
Let k be a field. We are interested in the families of r-dimensional subspaces of kn with the following transversality property: any linear subspace of kn of dimension n-r is transversal to at least...
Classical and intuitionistic logic are asymptotically identical (2007)
Hervé Fournier, Danièle Gardy, Antoine Genitrini, Marek Zaionc
This paper considers logical formulas built on the single binary connector of implication and a finite number of variables. When the number of variables becomes large, we prove the following...
A tight lower bound for computing the diameter of a 3D convex polytope (2007)
Hervé Fournier, Antoine Vigneron
The diameter of a set P of n points in R d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure...
Classical and intuitionistic logic are asymptotically identical (2007)
Hervé Fournier, Danièle Gardy, Antoine Genitrini, Marek Zaionc
This paper considers logical formulas built on the single binary connector of implication and a finite number of variables. When the number of variables becomes large, we prove the following...
Lower bounds for geometric diameter problems (2006)
Hervé Fournier, Antoine Vigneron
The diameter of a set P of n points in R d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure...
Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. (2002)
Chistov, Alexander, Fournier, Hervé, Gurvits, Leonid, Koiran, Pascal
(eng) Let E be a vector space of dimension n over an infinite field K. We give polynomial time constructions of families of r-dimensional subspaces of E with the following transversality property:...
Vandermonde Matrices, NP-Completeness, (2002)
École Normale, Supérieure Lyon, Er Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran, ...
Let K be an infinite field. We give polynomial time constructions of families of r-dimensional subspaces of K n with the following transversality property: any linear subspace of K n of dimension n...
Quantifier rank for parity of embedded finite models. (2001)
(eng) We prove some lower bounds for quantifier rank of formulas expressing parity of a finite set I of bounded cardinal embedded in an algebraically closed field or an ordered Q-vector space. We...
Sparse NP-complete problems of the reals with addition. (2000)
(eng) An analog of Mahaney's Theorem was shown, stating that there is no sparse NP-complete problem over the reals with addition and equality - here sparse is defined in terms of dimension. We extend...
Lower bounds are not easier over the reals: inside PH. (1999)
Fournier, Hervé, Koiran, Pascal
(eng) We prove that all NP problems over the reals with addition and order can be solved in polynomial time with the help of a boolean NP oracle. As a consequence, the ``P = NP?'' question over the...
Lower Bounds Are not Easier over the Reals: Inside PH (1999)
Hervé Fournier, Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran March, ...
We prove that all NP problems over the reals with addition and order can be solved in polynomial time with the help of a boolean NP oracle. As a consequence, the "P = NP?" question over the...
Are lower bounds easier over the reals ?. (1997)
Koiran, Pascal, Fournier, Hervé
(eng) We show that proving lower bounds in algebraic models of computation may not be easier than in the standard Turing machine model. For instance, a superpolynomial lower bound on the size of an...