Adversary lower bounds for nonadaptive quantum algorithms (2008)
Koiran, Pacal, Landes, Jürgen, Portier, Natacha, Yao, Penghui
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Characterizing Valiant’s algebraic complexity (2008)
École Normale, Supérieure Lyon, Guillaume Malod, École Normale, Supérieure Lyon, Guillaume Malod, ...
classes
Adversary lower bounds for nonadaptive quantum algorithms (2008)
Koiran, Pacal, Portier, Natacha, Yao, Penghui, Landes, Jürgen
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Adversary lower bounds for nonadaptive quantum algorithms (2008)
Koiran, Pacal, Portier, Natacha, Yao, Penghui, Landes, Jürgen
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Adversary lower bounds for nonadaptive quantum algorithms (2008)
Koiran, Pascal, Landes, Jürgen, Portier, Natacha, Yao, Penghui
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Adversary lower bounds for nonadaptive quantum algorithms (2008)
Koiran, Pascal, Landes, Jürgen, Portier, Natacha, Yao, Penghui
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
for Generic Curves and a Decision Algorithm for the Limit Theory (2007)
Superieure Lyon, Unite Mixte, Natacha Portier September, Ecole Normale, Ecole Normale, ...
It was recently shown that the theories of generic algebraic curves converge to a limit theory as their degrees go to innity. In this paper we give quantitative versions of this result and other...
4.29> 1 = a 2 n g. Si ¯ x = (x 1 ; :::; x n ) est un uple d"el'ements de K, on s'int'eresse `a la question ¯ x 2 X ? Etudier la complexit'e des probl `emes, c'est...
A Rank Theorem for Vandermonde Matrices (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran, Pascal Koiran, ...
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the \limit theory of generic polynomials".
Vincent D. Blondel, Natacha Portier
presence of a zero in an integer linear recurrent
Pascal Koiran Natacha, Pascal Koiran, Natacha Portier, Gilles Villard
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the "limit theory of generic polynomials". 2003 Elsevier...
On the probabilistic query complexity of transitively symmetric problems (2006)
Koiran, Pascal, Nesme, Vincent, Portier, Natacha
20 pages, figures, 24 références bibliographiques
On the Probabilistic Query Complexity of Transitively Symmetric Problems (2006)
École Normale, Supérieure Lyon, Pascal Koiran, Vincent Nesme, Natacha Portier, École Normale, ...
We obtain optimal lower bounds on the nonadaptive probabilistic query complexity of a class of problems defined by a rather weak symmetry condition. In fact, for each problem in this class, given a...
The Quantum Query Complexity of the Abelian Hidden Subgroup Problem. (2005)
Koiran, Pascal, Nesme, Vincent, Portier, Natacha
(eng) Simon in his FOCS'94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the...
A quantum lower bound for the query complexity of Simon's problem (2005)
Koiran, Pascal, Nesme, Vincent, Portier, Natacha
Simon in his FOCS'94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden...
On the Probabilistic Query Complexity of Transitively Symmetric Problems (2005)
Koiran, Pacal, Nesme, Vincent, Portier, Natacha
We obtain optimal lower bounds on the nonadaptive probabilistic query complexity of a class of problems defined by a rather weak symmetry condition. In fact, for each problem in this class, given a...
On the Probabilistic Query Complexity of Transitively Symmetric Problems (2005)
Koiran, Pacal, Nesme, Vincent, Portier, Natacha
We obtain optimal lower bounds on the nonadaptive probabilistic query complexity of a class of problems defined by a rather weak symmetry condition. In fact, for each problem in this class, given a...
Decidable and undecidable problems about quantum automata (2005)
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier
Abstract. We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on...
Decidable and undecidable problems about quantum automata (2003)
Blondel, Vincent D., Jeandel, Emmanuel, Koiran, Pascal, Portier, Natacha
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether...
Decidable and undecidable problems about quantum automata. (2003)
Blondel, Vincent D., Jeandel, Emmanuel, Koiran, Pascal, Portier, Natacha
(eng) We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether...
A rank theorem for Vandermonde matrices (2003)
Pascal Koiran, Natacha Portier, Gilles Villard
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the "limit theory of generic polynomials". 1
The Set of Realizations of a Max-Plus Linear Sequence Is Semi-Polyhedral (2003)
Vincent Blondel, Stephane Gaubert, Natacha Portier
We show that the set of realizations of dimension n of a max-plus linear sequence is a nite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an...
The presence of a zero in an integer linear recurrent sequence is NP-hard to decide (1999)
Vincent Blondel, Natacha Portier, Natacha Portier
We show that the problem of determining if a given integer linear recurrent sequence has a zero is NP-hard. It is not known whether this problem is decidable or not. With a similar argument we show...
R'esolutions universelles pour des probl`emes NP-complets
Natacha Portier Consid'erons, Natacha Portier
F33.43> n ) sur R tels que le polynome a 0 + a 1 X + ::: + a n X n admette une racine r'eelle. Si ¯a = (a 0 ; :::; a n ), se demander si ¯ a 2 X 0 , c'est se demander si le polynome a...