Pascal Koiran

According to our database, Pascal Koiran authored at least 105 papers between 1991 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

An efficient uniqueness theorem for overcomplete tensor decomposition.

Pascal Koiran

CoRR, 2024

Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number.

Pascal Koiran, Subhayan Saha

CoRR, 2024

On the uniqueness and computation of commuting extensions.

Pascal Koiran

CoRR, 2024

2023

Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond.

Pascal Koiran, Subhayan Saha

Comput. Complex., December, 2023

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision.

Pascal Koiran, Subhayan Saha

Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

2022

Black Box Absolute Reconstruction for Sums of Powers of Linear Forms.

Pascal Koiran, Subhayan Saha

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

Derandomization and absolute reconstruction for sums of powers of linear forms.

Pascal Koiran, Mateusz Skomra

Theor. Comput. Sci., 2021

Computing the multilinear factors of lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

J. Symb. Comput., 2021

2020

Reconstruction algorithms for sums of affine powers.

Ignacio García-Marco, Pascal Koiran, Timothée Pecatte

J. Symb. Comput., 2020

On tensor rank and commuting matrices.

Pascal Koiran

CoRR, 2020

2019

Root separation for trinomials.

Pascal Koiran

J. Symb. Comput., 2019

Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective.

Pascal Koiran

CoRR, 2019

Intersection multiplicity of a sparse curve and a low-degree curve.

Pascal Koiran, Mateusz Skomra

CoRR, 2019

2018

On the linear independence of shifted powers.

Pascal Koiran, Timothée Pecatte, Ignacio García-Marco

J. Complex., 2018

Orbits of monomials and factorization into products of linear forms.

Pascal Koiran, Nicolas Ressayre

CoRR, 2018

Polynomial Equivalence Problems for Sum of Affine Powers.

Ignacio García-Marco, Pascal Koiran, Timothée Pecatte

Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, 2018

2017

Lower bounds by Birkhoff interpolation.

Ignacio García-Marco, Pascal Koiran

J. Complex., 2017

On the Complexity of Partial Derivatives.

Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2015

A Wronskian approach to the real τ-conjecture.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

J. Symb. Comput., 2015

A $$\tau $$ τ -Conjecture for Newton Polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

Found. Comput. Math., 2015

On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem.

Pascal Koiran, Natacha Portier, Sébastien Tavenas

Discret. Comput. Geom., 2015

Log-Concavity and Lower Bounds for Arithmetic Circuits.

Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Lower Bounds for Sums of Powers of Low Degree Univariates.

Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Hidden Cliques and the Certification of the Restricted Isometry Property.

Pascal Koiran, Anastasios Zouzias

IEEE Trans. Inf. Theory, 2014

2013

On the complexity of the multivariate resultant.

Bruno Grenet, Pascal Koiran, Natacha Portier

J. Complex., 2013

Computational Counting (Dagstuhl Seminar 13031).

Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran

Dagstuhl Reports, 2013

A tau-conjecture for Newton polygons.

Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé

CoRR, 2013

Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent.

Pascal Koiran, Natacha Portier, J. Maurice Rojas

CoRR, 2013

Factoring bivariate lacunary polynomials without heights.

Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2012

Arithmetic circuits: The chasm at depth four gets wider.

Pascal Koiran

Theor. Comput. Sci., 2012

Upper bounds on real roots and lower bounds for the permanent.

Pascal Koiran

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2012

2011

On the expressive power of CNF formulas of bounded tree- and clique-width.

Irénée Briquel, Pascal Koiran, Klaus Meer

Discret. Appl. Math., 2011

On the Certification of the Restricted Isometry Property

Pascal Koiran, Anastasios Zouzias

CoRR, 2011

Interpolation in Valiant's Theory.

Pascal Koiran, Sylvain Perifel

Comput. Complex., 2011

Symmetric Determinantal Representation of Weakly-Skew Circuits.

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Shallow circuits with high-powered inputs.

Pascal Koiran

Proceedings of the Innovations in Computer Science, 2011

The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent.

Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Adversary lower bounds for nonadaptive quantum algorithms.

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao

J. Comput. Syst. Sci., 2010

Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier

CoRR, 2010

The Multivariate Resultant Is NP-hard in Any Characteristic.

Bruno Grenet, Pascal Koiran, Natacha Portier

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

VPSPACE and a transfer theorem over the complex field.

Pascal Koiran, Sylvain Perifel

Theor. Comput. Sci., 2009

The multivariate resultant lies between NP and AM

Bruno Grenet, Pascal Koiran, Natacha Portier

CoRR, 2009

A hitting set construction, with application to arithmetic circuit lower bounds

Pascal Koiran

CoRR, 2009

Toward a Dichotomy Theorem for Polynomial Evaluation

Irénée Briquel, Pascal Koiran

CoRR, 2009

VPSPACE and a Transfer Theorem over the Reals.

Pascal Koiran, Sylvain Perifel

Comput. Complex., 2009

A Dichotomy Theorem for Polynomial Evaluation.

Irénée Briquel, Pascal Koiran

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent.

Pascal Koiran, Sylvain Perifel

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Finding a vector orthogonal to roughly half a collection of vectors.

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé

J. Complex., 2008

On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.

Pascal Koiran, Klaus Meer

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Expressing a fraction of two determinants as a determinant.

Erich L. Kaltofen, Pascal Koiran

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007

The complexity of two problems on arithmetic circuits.

Pascal Koiran, Sylvain Perifel

Theor. Comput. Sci., 2007

The quantum query complexity of the abelian hidden subgroup problem.

Pascal Koiran, Vincent Nesme, Natacha Portier

Theor. Comput. Sci., 2007

Decision Versus Evaluation in Algebraic Complexity.

Pascal Koiran

Proceedings of the Machines, Computations, and Universality, 5th International Conference, 2007

On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.

Uffe Flarup, Pascal Koiran, Laurent Lyaudet

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

Valiant's Model: From Exponential Sums to Exponential Products.

Pascal Koiran, Sylvain Perifel

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields.

Erich L. Kaltofen, Pascal Koiran

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

2005

Decidable and Undecidable Problems about Quantum Automata.

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier

SIAM J. Comput., 2005

Quantum automata and algebraic groups.

Harm Derksen, Emmanuel Jeandel, Pascal Koiran

J. Symb. Comput., 2005

Guest editors' preface.

Askold Khovanskii, Pascal Koiran, Teresa Krick, Gregorio Malajovich, Joseph F. Traub

J. Complex., 2005

Valiant's model and the cost of computing integers.

Pascal Koiran

Comput. Complex., 2005

On the complexity of factoring bivariate supersparse (Lacunary) polynomials.

Erich L. Kaltofen, Pascal Koiran

Proceedings of the Symbolic and Algebraic Computation, 2005

A Quantum Lower Bound for the Query Complexity of Simon's Problem.

Pascal Koiran, Vincent Nesme, Natacha Portier

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2003

The theory of Liouville functions.

Pascal Koiran

J. Symb. Log., 2003

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces.

Alexander L. Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran

Found. Comput. Math., 2003

2002

La Limite des Theories de Courbes Generiques.

Olivier Chapuis, Ehud Hrushovski, Pascal Koiran, Bruno Poizat

J. Symb. Log., 2002

Transfer theorems via sign conditions.

Pascal Koiran

Inf. Process. Lett., 2002

2001

Deciding stability and mortality of piecewise affine dynamical systems.

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis

Theor. Comput. Sci., 2001

The Stability of Saturated Linear Dynamical Systems Is Undecidable.

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

J. Comput. Syst. Sci., 2001

The topological entropy of iterated piecewise affine maps is uncomputable.

Pascal Koiran

Discret. Math. Theor. Comput. Sci., 2001

Back-and-forth systems for generic curves and a decision algorithm for the limit theory.

Pascal Koiran, Natacha Portier

Ann. Pure Appl. Log., 2001

2000

The Complexity of Local Dimensions for Constructible Sets.

Pascal Koiran

J. Complex., 2000

Guest Editors' Preface.

Jean-Pierre Dedieu, Pascal Koiran

J. Complex., 2000

Circuits versus Trees in Algebraic Complexity.

Pascal Koiran

Proceedings of the STACS 2000, 2000

Lower Bounds Are Not Easier over the Reals: Inside PH.

Hervé Fournier, Pascal Koiran

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Closed-for Analytic Maps in One and Two Dimensions can Simulate Universal Turing Machines.

Pascal Koiran, Cristopher Moore

Theor. Comput. Sci., 1999

Elimination of Parameters in the Polynomial Hierarchy.

Pascal Koiran

Theor. Comput. Sci., 1999

Definability of Geometric Properties in Algebraically Closed Fields.

Olivier Chapuis, Pascal Koiran

Math. Log. Q., 1999

A Polynomial Time Algorithm for Diophantine Equations in One Variable.

Felipe Cucker, Pascal Koiran, Steve Smale

J. Symb. Comput., 1999

The Real Dimension Problem Is NPR-Complete.

Pascal Koiran

J. Complex., 1999

Saturation and Stability in the Theory of Computation over the Reals.

Olivier Chapuis, Pascal Koiran

Ann. Pure Appl. Log., 1999

1998

Vapnik-Chervonenkis Dimension of Recurrent Neural Networks.

Pascal Koiran, Eduardo D. Sontag

Discret. Appl. Math., 1998

Are Lower Bounds Easier over the Reals?

Hervé Fournier, Pascal Koiran

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Neural Networks with Quadratic VC Dimension.

Pascal Koiran, Eduardo D. Sontag

J. Comput. Syst. Sci., 1997

A Weak Version of the Blum, Shub, and Smale Model.

Pascal Koiran

J. Comput. Syst. Sci., 1997

Approximation and Learning of Convex Superpositions.

Leonid Gurvits, Pascal Koiran

J. Comput. Syst. Sci., 1997

Elimination of Constants from Machines over Algebraically Closed Fields.

Pascal Koiran

J. Complex., 1997

Complexity and Dimension.

Felipe Cucker, Pascal Koiran, Martín Matamala

Inf. Process. Lett., 1997

Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties.

Pascal Koiran

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

A Family of Universal Recurrent Networks.

Pascal Koiran

Theor. Comput. Sci., 1996

Hilbert's Nullstellensatz Is in the Polynomial Hierarchy.

Pascal Koiran

J. Complex., 1996

1995

Computing over the Reals with Addition and Order: Higher Complexity Classes.

Felipe Cucker, Pascal Koiran

J. Complex., 1995

VC Dimension in Circuit Complexity

Pascal Koiran

Electron. Colloquium Comput. Complex., 1995

On real Turing machines that toss coins.

Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Approximating the Volume of Definable Sets.

Pascal Koiran

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Computability with Low-Dimensional Dynamical Systems.

Pascal Koiran, Michel Cosnard, Max H. Garzon

Theor. Comput. Sci., 1994

Computing over the Reals with Addition and Order.

Pascal Koiran

Theor. Comput. Sci., 1994

Dynamics of Discrete Time, Continuous State Hopfield Networks.

Pascal Koiran

Neural Comput., 1994

Bounds on the Number of Units for Computing Arbitrary Dichotomies by Multilayer Perceptrons.

Michel Cosnard, Pascal Koiran, Hélène Paugam-Moisy

J. Complex., 1994

Efficient Learning of Continuous Neural Networks.

Pascal Koiran

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

On the complexity of approximating mappings using feedforward networks.

Pascal Koiran

Neural Networks, 1993

Computability Properties of Low-dimensional Dynamical Systems.

Michel Cosnard, Max H. Garzon, Pascal Koiran

Proceedings of the STACS 93, 1993

A Weak Version of the Blum, Shub & Smale model

Pascal Koiran

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Relations between Models of Parallel Abstract Machines.

Michel Cosnard, Pascal Koiran

Proceedings of the Parallel Architectures and Their Efficient Use, 1992

Complexity Issues in Neural Network Computations.

Michel Cosnard, Pascal Koiran, Hélène Paugam-Moisy

Proceedings of the LATIN '92, 1992

1991

Meta-Level Interpretation of CLP(Lists).

Jacques Cohen, Pascal Koiran, Catherine Perrin

Proceedings of the Constraint Logic Programming, 1991