Pascal Koiran

ORCID

Publication Activity (10 Years)

Years Active: 1991-2024
Publications (10 Years): 33

Top Venues

Publications

Pascal Koiran
An efficient uniqueness theorem for overcomplete tensor decomposition. CoRR (2024)
Pascal Koiran
On the uniqueness and computation of commuting extensions. CoRR (2024)
Pascal Koiran, Subhayan Saha
Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number. CoRR (2024)
Pascal Koiran, Subhayan Saha
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond. Comput. Complex. 32 (2) (2023)
Pascal Koiran, Subhayan Saha
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision. CIAC (2023)
Pascal Koiran, Subhayan Saha
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision. CoRR (2022)
Pascal Koiran, Subhayan Saha
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. FSTTCS (2022)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Computing the multilinear factors of lacunary polynomials without heights. J. Symb. Comput. 104 (2021)
Pascal Koiran, Subhayan Saha
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. CoRR (2021)
Pascal Koiran, Mateusz Skomra
Derandomization and absolute reconstruction for sums of powers of linear forms. Theor. Comput. Sci. 887 (2021)
Pascal Koiran
On tensor rank and commuting matrices. CoRR (2020)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte
Reconstruction algorithms for sums of affine powers. J. Symb. Comput. 98 (2020)
Pascal Koiran, Mateusz Skomra
Intersection multiplicity of a sparse curve and a low-degree curve. CoRR (2019)
Pascal Koiran, Mateusz Skomra
Derandomization and absolute reconstruction for sums of powers of linear forms. CoRR (2019)
Pascal Koiran
Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective. CoRR (2019)
Pascal Koiran
Root separation for trinomials. J. Symb. Comput. 95 (2019)
Pascal Koiran, Timothée Pecatte, Ignacio García-Marco
On the linear independence of shifted powers. J. Complex. 45 (2018)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte
Polynomial Equivalence Problems for Sum of Affine Powers. ISSAC (2018)
Pascal Koiran, Nicolas Ressayre
Orbits of monomials and factorization into products of linear forms. CoRR (2018)
Ignacio García-Marco, Pascal Koiran
Lower bounds by Birkhoff interpolation. J. Complex. 39 (2017)
Pascal Koiran
Root Separation for Trinomials. CoRR (2017)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé
On the Complexity of Partial Derivatives. STACS (2017)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte
On the linear independence of shifted powers. CoRR (2017)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte
Reconstruction Algorithms for Sums of Affine Powers. ISSAC (2017)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé
On the complexity of partial derivatives. CoRR (2016)
Ignacio García-Marco, Pascal Koiran, Timothée Pecatte
Reconstruction Algorithms for Sums of Affine Powers. CoRR (2016)
Pascal Koiran, Natacha Portier, Sébastien Tavenas
On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem. Discret. Comput. Geom. 53 (1) (2015)
Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas
Log-concavity and lower bounds for arithmetic circuits. CoRR (2015)
Ignacio García-Marco, Pascal Koiran
Lower Bounds by Birkhoff Interpolation. CoRR (2015)
Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas
Log-Concavity and Lower Bounds for Arithmetic Circuits. MFCS (2) (2015)
Pascal Koiran, Natacha Portier, Sébastien Tavenas
A Wronskian approach to the real τ-conjecture. J. Symb. Comput. 68 (2015)
Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha
Lower Bounds for Sums of Powers of Low Degree Univariates. ICALP (1) (2015)
Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé
A $$\tau $$ τ -Conjecture for Newton Polygons. Found. Comput. Math. 15 (1) (2015)
Pascal Koiran, Anastasios Zouzias
Hidden Cliques and the Certification of the Restricted Isometry Property. IEEE Trans. Inf. Theory 60 (8) (2014)
Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé
A tau-conjecture for Newton polygons. CoRR (2013)
Bruno Grenet, Pascal Koiran, Natacha Portier
On the complexity of the multivariate resultant. J. Complex. 29 (2) (2013)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Computing the multilinear factors of lacunary polynomials without heights. CoRR (2013)
Pascal Koiran, Natacha Portier, J. Maurice Rojas
Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent. CoRR (2013)
Pascal Koiran, Natacha Portier, Sébastien Tavenas
On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem. CoRR (2013)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Factoring bivariate lacunary polynomials without heights. ISSAC (2013)
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran
Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 3 (1) (2013)
Bruno Grenet, Pascal Koiran, Natacha Portier
On the Complexity of the Multivariate Resultant CoRR (2012)
Pascal Koiran
Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci. 448 (2012)
Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
Factoring bivariate lacunary polynomials without heights CoRR (2012)
Pascal Koiran
Upper bounds on real roots and lower bounds for the permanent. ISSAC (2012)
Pascal Koiran, Anastasios Zouzias
Hidden cliques and the certification of the restricted isometry property CoRR (2012)
Pascal Koiran, Natacha Portier, Sébastien Tavenas
A Wronskian Approach to the real τ-conjecture CoRR (2012)
Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. FSTTCS (2011)
Irénée Briquel, Pascal Koiran, Klaus Meer
On the expressive power of CNF formulas of bounded tree- and clique-width. Discret. Appl. Math. 159 (1) (2011)
Pascal Koiran, Sylvain Perifel
Interpolation in Valiant's Theory. Comput. Complex. 20 (1) (2011)
Bruno Grenet, Erich Kaltofen, Pascal Koiran, Natacha Portier
Symmetric Determinantal Representation of Weakly-Skew Circuits. STACS (2011)
Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent CoRR (2011)
Pascal Koiran, Anastasios Zouzias
On the Certification of the Restricted Isometry Property CoRR (2011)
Pascal Koiran
Shallow circuits with high-powered inputs. ICS (2011)
Bruno Grenet, Pascal Koiran, Natacha Portier
The Multivariate Resultant Is NP-hard in Any Characteristic. MFCS (2010)
Pascal Koiran
Arithmetic circuits: the chasm at depth four gets wider CoRR (2010)
Bruno Grenet, Erich Kaltofen, Pascal Koiran, Natacha Portier
Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits CoRR (2010)
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao
Adversary lower bounds for nonadaptive quantum algorithms. J. Comput. Syst. Sci. 76 (5) (2010)
Pascal Koiran
Shallow Circuits with High-Powered Inputs CoRR (2010)
Pascal Koiran, Sylvain Perifel
VPSPACE and a transfer theorem over the complex field. Theor. Comput. Sci. 410 (50) (2009)
Irénée Briquel, Pascal Koiran
A Dichotomy Theorem for Polynomial Evaluation. MFCS (2009)
Pascal Koiran, Sylvain Perifel
VPSPACE and a Transfer Theorem over the Reals. Comput. Complex. 18 (4) (2009)
Pascal Koiran, Sylvain Perifel
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent CoRR (2009)
Pascal Koiran, Sylvain Perifel
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. Computational Complexity Conference (2009)
Pascal Koiran
A hitting set construction, with application to arithmetic circuit lower bounds CoRR (2009)
Bruno Grenet, Pascal Koiran, Natacha Portier
The multivariate resultant lies between NP and AM CoRR (2009)
Irénée Briquel, Pascal Koiran
Toward a Dichotomy Theorem for Polynomial Evaluation CoRR (2009)
Erich Kaltofen, Pascal Koiran
Expressing a fraction of two determinants as a determinant. ISSAC (2008)
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao
Adversary lower bounds for nonadaptive quantum algorithms CoRR (2008)
Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé
Finding a vector orthogonal to roughly half a collection of vectors. J. Complex. 24 (1) (2008)
Pascal Koiran, Klaus Meer
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width. WG (2008)
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao
Adversary Lower Bounds for Nonadaptive Quantum Algorithms. WoLLIC (2008)
Pascal Koiran, Sylvain Perifel
VPSPACE and a transfer theorem over the complex field CoRR (2007)
Pascal Koiran, Sylvain Perifel
Interpolation in Valiant's theory CoRR (2007)
Laurent Lyaudet, Pascal Koiran, Uffe Flarup
On the expressive power of planar perfect matching and permanents of bounded treewidth matrices CoRR (2007)
Pascal Koiran
Decision Versus Evaluation in Algebraic Complexity. MCU (2007)
Pascal Koiran, Sylvain Perifel
VPSPACE and a Transfer Theorem over the Complex Field. MFCS (2007)
Pascal Koiran, Sylvain Perifel
VPSPACE and a Transfer Theorem over the Reals. STACS (2007)
Pascal Koiran, Vincent Nesme, Natacha Portier
The quantum query complexity of the abelian hidden subgroup problem. Theor. Comput. Sci. 380 (1-2) (2007)
Pascal Koiran, Sylvain Perifel
The complexity of two problems on arithmetic circuits. Theor. Comput. Sci. 389 (1-2) (2007)
Uffe Flarup, Pascal Koiran, Laurent Lyaudet
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. ISAAC (2007)
Pascal Koiran, Sylvain Perifel
VPSPACE and a Transfer Theorem over the Reals CoRR (2006)
Erich Kaltofen, Pascal Koiran
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. ISSAC (2006)
Pascal Koiran, Sylvain Perifel
Valiant's Model: From Exponential Sums to Exponential Products. MFCS (2006)
Pascal Koiran
Valiant's model and the cost of computing integers. Comput. Complex. 13 (3-4) (2005)
Erich Kaltofen, Pascal Koiran
On the complexity of factoring bivariate supersparse (Lacunary) polynomials. ISSAC (2005)
Harm Derksen, Emmanuel Jeandel, Pascal Koiran
Quantum automata and algebraic groups. J. Symb. Comput. 39 (3-4) (2005)
Pascal Koiran, Vincent Nesme, Natacha Portier
A Quantum Lower Bound for the Query Complexity of Simon's Problem. ICALP (2005)
Askold Khovanskii, Pascal Koiran, Teresa Krick, Gregorio Malajovich, Joseph F. Traub
Guest editors' preface. J. Complex. 21 (1) (2005)
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier
Decidable and Undecidable Problems about Quantum Automata. SIAM J. Comput. 34 (6) (2005)
Pascal Koiran, Vincent Nesme, Natacha Portier
A quantum lower bound for the query complexity of Simon's problem CoRR (2005)
Pascal Koiran
Valiant's model and the cost of computing integers Electron. Colloquium Comput. Complex. (003) (2004)
Pascal Koiran
The theory of Liouville functions. J. Symb. Log. 68 (2) (2003)
Alexander L. Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran
Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. Found. Comput. Math. 3 (4) (2003)
Pascal Koiran
Transfer theorems via sign conditions. Inf. Process. Lett. 81 (2) (2002)
Olivier Chapuis, Ehud Hrushovski, Pascal Koiran, Bruno Poizat
La Limite des Theories de Courbes Generiques. J. Symb. Log. 67 (1) (2002)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis
Deciding stability and mortality of piecewise affine dynamical systems. Theor. Comput. Sci. 255 (1-2) (2001)
Pascal Koiran, Natacha Portier
Back-and-forth systems for generic curves and a decision algorithm for the limit theory. Ann. Pure Appl. Log. 111 (3) (2001)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
The Stability of Saturated Linear Dynamical Systems Is Undecidable. J. Comput. Syst. Sci. 62 (3) (2001)
Pascal Koiran
The topological entropy of iterated piecewise affine maps is uncomputable. Discret. Math. Theor. Comput. Sci. 4 (2) (2001)

Pascal Koiran.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Pascal Koiran