Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable (2009)
Mayordomo, Elvira, Moser, Philippe, Perifel, Sylvain
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation, and in particular calls for a formulation of information-lossless stack or...
Koiran, Pascal, Perifel, Sylvain
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Koiran, Pascal, Perifel, Sylvain
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Koiran, Pascal, Perifel, Sylvain
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Pilar Albert, Elvira Mayordomo, Sylvain Perifel
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation [6, 9], and in particular calls for a formulation of information-lossless stack or...
Albert, Pilar, Mayordomo, Elvira, Moser, Philippe, Perifel, Sylvain
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan and Shankar 2006, League and Eng 2007), and in particular calls for a...
Albert, Pilar, Mayordomo, Elvira, Moser, Philippe, Perifel, Sylvain
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan and Shankar 2006, League and Eng 2007), and in particular calls for a...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2008)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stephan
Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most...
05. Pushdown Compression (2008)
Albert, Pilar, Mayordomo, Elvira, Moser, Philip, Perifel, Sylvain
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan and Shankar 2006, League and Eng 2007), and in particular calls for a...
Albert, Pilar, Mayordomo, Elvira, Moser, Philippe, Perifel, Sylvain
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation, and in particular calls for a formulation of information-lossless stack or...
Interpolation in Valiant's theory (2007)
Koiran, Pascal, Perifel, Sylvain
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that...
Albert, Pilar, Mayordomo, Elvira, Moser, Philippe, Perifel, Sylvain
The pressing need for eficient compression schemes for XML documents has recently been focused on stack computation [6, 9], and in particular calls for a formulation of information-lossless stack or...
VPSPACE and a transfer theorem over the complex field (2007)
Koiran, Pascal, Perifel, Sylvain
We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation...
VPSPACE and a transfer theorem over the complex field (2007)
Koiran, Pascal, Perifel, Sylvain
We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2007)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomassé, Stéphan
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F_2)^d, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of...
The Complexity of two Problems on Arithmetic Circuits (2007)
Koiran, Pascal, Perifel, Sylvain
By using arithmetic circuits, encoding multivariate polynomials may be drastically more efficient than writing down the list of monomials. Via the study of two examples, we show however that such an...
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...
Interpolation in Valiant's theory (2007)
Koiran, Pascal, Perifel, Sylvain
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that...
Interpolation in Valiant's theory (2007)
Koiran, Pascal, Perifel, Sylvain
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that...
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...
The Complexity of two Problems on Arithmetic Circuits (2007)
Koiran, Pascal, Perifel, Sylvain
By using arithmetic circuits, encoding multivariate polynomials may be drastically more efficient than writing down the list of monomials. Via the study of two examples, we show however that such an...
Finding a Vector Orthogonal to Roughly Half a Collection of Vectors (2007)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomassé, Stéphan
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F_2)^d, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of...
VPSPACE and a transfer theorem over the complex field (2007)
Koiran, Pascal, Perifel, Sylvain
We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation...
VPSPACE and a transfer theorem over the reals (2007)
Pascal Koiran, Sylvain Perifel
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
Symmetry of information and nonuniform lower bounds (2006)
In a first part we provide another proof of the result of [Homer, Mocas 1995] that for all constant c, the class EXP is not included in P/(n^c) . The proof is based on a simple diagonalization,...
VPSPACE and a Transfer Theorem over the Reals (2006)
Koiran, Pascal, Perifel, Sylvain
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
VPSPACE and a Transfer Theorem over the Reals (2006)
Koiran, Pascal, Perifel, Sylvain
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
VPSPACE and a Transfer Theorem over the Reals (2006)
Koiran, Pascal, Perifel, Sylvain
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
Valiant's model: from exponential sums to exponential products (2006)
Perifel, Sylvain, Koiran, Pascal
We study the power of big products for computing multivariate polynomials in a Valiant-like framework. More precisely, we define a new class \vpip as the set of families of polynomials that are...
Valiant's model : from exponential sums to exponential products (2006)
Koiran, Pascal, Perifel, Sylvain
12 pages, 18 références bibliographiques
Finding a vector orthogonal to roughly half a collection of vectors (2006)
Charbit, Pierre, Jeandel, Emmanuel, Koiran, Pascal, Perifel, Sylvain, Thomasse, Stefan
11 pages, 16 références bibliographiques
Valiant's model: from exponential sums to exponential products (2006)
Perifel, Sylvain, Koiran, Pascal
We study the power of big products for computing multivariate polynomials in a Valiant-like framework. More precisely, we define a new class \vpip as the set of families of polynomials that are...
VPSPACE and a Transfer Theorem over the Reals (2006)
Koiran, Pascal, Perifel, Sylvain
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
Symmetry of information and nonuniform lower bounds (2006)
In the first part we provide another proof of the result of [Homer, Mocas 1995] that for all constant c, the class EXP is not included in P/(n^c) . The proof is based on a simple diagonalization,...
Symmetry of information and nonuniform lower bounds (2006)
In the first part we provide another proof of the result of [Homer, Mocas 1995] that for all constant c, the class EXP is not included in P/(n^c) . The proof is based on a simple diagonalization,...
VPSPACE and a Transfer Theorem over the Reals (2006)
Koiran, Pascal, Perifel, Sylvain
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that...
Valiant's model: from exponential sums to exponential products (2006)
Perifel, Sylvain, Koiran, Pascal
We study the power of big products for computing multivariate polynomials in a Valiant-like framework. More precisely, we define a new class \vpip as the set of families of polynomials that are...
VPSPACE and a transfer theorem over the complex field (2006)
Pascal Koiran, Sylvain Perifel, École Normale, Supérieure Lyon
Abstract. We extend the transfer theorem of [13] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of...
Number of Variables and Expressive Power of First-Order Logic on Finite Ordered Structures (2003)
It is an open question whether increasing the number of variables increases the expressive power of rst-order logic on nite ordered structures.