mirage

Browsing Sciences Physiques et Mathématiques / Physics and Mathematics by Author "Koiran, Pascal"

DSpace/Manakin Repository

Browsing Sciences Physiques et Mathématiques / Physics and Mathematics by Author "Koiran, Pascal"

Sort by: Order: Results:

  • Are lower bounds easier over the reals ?
    Laboratoire de l'informatique du parallélisme; Koiran, Pascal; Fournier, Hervé (1997-10)
    (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 algebraic circuit solving ...
  • A polynomial time algorithm for diophantine equations in one variable.
    Laboratoire de l'informatique du parallélisme; Cucker, Felipe; Koiran, Pascal; Smale, Steve (1997-11)
    (eng) We show that the integer roots of of a univariate polynomial with integer coefficients can be computed in polynomial time. This result holds for the classical (i.e. Turing) model of computation and a sparse representation ...
  • The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.
    Laboratoire de l'informatique du parallélisme; Koiran, Pascal; Nesme, Vincent; Portier, Natacha (2005-04)
    (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 hidden subgroup problems. ...
  • The Real Dimension Problem is NPR-complete.
    Laboratoire de l'informatique du parallélisme; Koiran, Pascal (1997-10)
    (eng) We show that computing the dimension of a semi-algebraic set of R^n is an NP-complete problem in the Blum-Shub-Smale model of computation over the reals. Since this problem is easily seen to be NPR-hard, the main ...
  • The topological entropy of iterated piecewise affine maps is uncomputable.
    Laboratoire de l'informatique du parallélisme; Koiran, Pascal (2000-11)
    (eng) We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise affine function in dimension 4. The same result holds for saturated linear functions in unbounded ...
  • Transfer theorems via sign conditions
    Laboratoire de l'informatique du parallélisme; Koiran, Pascal (2000-03)
    (eng) We show that P = PSPACE implies the collapse of the boolean polynomial hierarchy over any structure which admits ``efficient enumeration of sign conditions''. This fairly rich class of structures contains in particular ...

Search DSpace


Advanced Search

Browse

My Account

Bookmark and Share