Pascal Koiran

Orcid: 0000-0003-3405-7155

Affiliations:
  • ENS Lyon, France


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
An efficient uniqueness theorem for overcomplete tensor decomposition.
CoRR, 2024

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

On the uniqueness and computation of commuting extensions.
CoRR, 2024

2023
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond.
Comput. Complex., December, 2023

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision.
Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

2022
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms.
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.
Theor. Comput. Sci., 2021

Computing the multilinear factors of lacunary polynomials without heights.
J. Symb. Comput., 2021

2020
Reconstruction algorithms for sums of affine powers.
J. Symb. Comput., 2020

On tensor rank and commuting matrices.
CoRR, 2020

2019
Root separation for trinomials.
J. Symb. Comput., 2019

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

Intersection multiplicity of a sparse curve and a low-degree curve.
CoRR, 2019

2018
On the linear independence of shifted powers.
J. Complex., 2018

Orbits of monomials and factorization into products of linear forms.
CoRR, 2018

Polynomial Equivalence Problems for Sum of Affine Powers.
Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, 2018

2017
Lower bounds by Birkhoff interpolation.
J. Complex., 2017

On the Complexity of Partial Derivatives.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2015
A Wronskian approach to the real τ-conjecture.
J. Symb. Comput., 2015

A $$\tau $$ τ -Conjecture for Newton Polygons.
Found. Comput. Math., 2015

On the Intersection of a Sparse Curve and a Low-Degree Curve: A Polynomial Version of the Lost Theorem.
Discret. Comput. Geom., 2015

Log-Concavity and Lower Bounds for Arithmetic Circuits.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Lower Bounds for Sums of Powers of Low Degree Univariates.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Hidden Cliques and the Certification of the Restricted Isometry Property.
IEEE Trans. Inf. Theory, 2014

2013
On the complexity of the multivariate resultant.
J. Complex., 2013

Computational Counting (Dagstuhl Seminar 13031).
Dagstuhl Reports, 2013

A tau-conjecture for Newton polygons.
CoRR, 2013

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

Factoring bivariate lacunary polynomials without heights.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2012
Arithmetic circuits: The chasm at depth four gets wider.
Theor. Comput. Sci., 2012

Upper bounds on real roots and lower bounds for the permanent.
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.
Discret. Appl. Math., 2011

On the Certification of the Restricted Isometry Property
CoRR, 2011

Interpolation in Valiant's Theory.
Comput. Complex., 2011

Symmetric Determinantal Representation of Weakly-Skew Circuits.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Shallow circuits with high-powered inputs.
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.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010
Adversary lower bounds for nonadaptive quantum algorithms.
J. Comput. Syst. Sci., 2010

Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits
CoRR, 2010

The Multivariate Resultant Is NP-hard in Any Characteristic.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
VPSPACE and a transfer theorem over the complex field.
Theor. Comput. Sci., 2009

The multivariate resultant lies between NP and AM
CoRR, 2009

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

Toward a Dichotomy Theorem for Polynomial Evaluation
CoRR, 2009

VPSPACE and a Transfer Theorem over the Reals.
Comput. Complex., 2009

A Dichotomy Theorem for Polynomial Evaluation.
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.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
Finding a vector orthogonal to roughly half a collection of vectors.
J. Complex., 2008

On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Expressing a fraction of two determinants as a determinant.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007
The complexity of two problems on arithmetic circuits.
Theor. Comput. Sci., 2007

The quantum query complexity of the abelian hidden subgroup problem.
Theor. Comput. Sci., 2007

Decision Versus Evaluation in Algebraic Complexity.
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.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
Valiant's Model: From Exponential Sums to Exponential Products.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

2005
Decidable and Undecidable Problems about Quantum Automata.
SIAM J. Comput., 2005

Quantum automata and algebraic groups.
J. Symb. Comput., 2005

Guest editors' preface.
J. Complex., 2005

Valiant's model and the cost of computing integers.
Comput. Complex., 2005

On the complexity of factoring bivariate supersparse (Lacunary) polynomials.
Proceedings of the Symbolic and Algebraic Computation, 2005

A Quantum Lower Bound for the Query Complexity of Simon's Problem.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2003
The theory of Liouville functions.
J. Symb. Log., 2003

Vandermonde Matrices, NP-Completeness, and Transversal Subspaces.
Found. Comput. Math., 2003

2002
La Limite des Theories de Courbes Generiques.
J. Symb. Log., 2002

Transfer theorems via sign conditions.
Inf. Process. Lett., 2002

2001
Deciding stability and mortality of piecewise affine dynamical systems.
Theor. Comput. Sci., 2001

The Stability of Saturated Linear Dynamical Systems Is Undecidable.
J. Comput. Syst. Sci., 2001

The topological entropy of iterated piecewise affine maps is uncomputable.
Discret. Math. Theor. Comput. Sci., 2001

Back-and-forth systems for generic curves and a decision algorithm for the limit theory.
Ann. Pure Appl. Log., 2001

2000
The Complexity of Local Dimensions for Constructible Sets.
J. Complex., 2000

Guest Editors' Preface.
J. Complex., 2000

Circuits versus Trees in Algebraic Complexity.
Proceedings of the STACS 2000, 2000

Lower Bounds Are Not Easier over the Reals: Inside PH.
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.
Theor. Comput. Sci., 1999

Elimination of Parameters in the Polynomial Hierarchy.
Theor. Comput. Sci., 1999

Definability of Geometric Properties in Algebraically Closed Fields.
Math. Log. Q., 1999

A Polynomial Time Algorithm for Diophantine Equations in One Variable.
J. Symb. Comput., 1999

The Real Dimension Problem Is NPR-Complete.
J. Complex., 1999

Saturation and Stability in the Theory of Computation over the Reals.
Ann. Pure Appl. Log., 1999

1998
Vapnik-Chervonenkis Dimension of Recurrent Neural Networks.
Discret. Appl. Math., 1998

Are Lower Bounds Easier over the Reals?
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
Neural Networks with Quadratic VC Dimension.
J. Comput. Syst. Sci., 1997

A Weak Version of the Blum, Shub, and Smale Model.
J. Comput. Syst. Sci., 1997

Approximation and Learning of Convex Superpositions.
J. Comput. Syst. Sci., 1997

Elimination of Constants from Machines over Algebraically Closed Fields.
J. Complex., 1997

Complexity and Dimension.
Inf. Process. Lett., 1997

Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
A Family of Universal Recurrent Networks.
Theor. Comput. Sci., 1996

Hilbert's Nullstellensatz Is in the Polynomial Hierarchy.
J. Complex., 1996

1995
Computing over the Reals with Addition and Order: Higher Complexity Classes.
J. Complex., 1995

VC Dimension in Circuit Complexity
Electron. Colloquium Comput. Complex., 1995

On real Turing machines that toss coins.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Approximating the Volume of Definable Sets.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Computability with Low-Dimensional Dynamical Systems.
Theor. Comput. Sci., 1994

Computing over the Reals with Addition and Order.
Theor. Comput. Sci., 1994

Dynamics of Discrete Time, Continuous State Hopfield Networks.
Neural Comput., 1994

Bounds on the Number of Units for Computing Arbitrary Dichotomies by Multilayer Perceptrons.
J. Complex., 1994

Efficient Learning of Continuous Neural Networks.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
On the complexity of approximating mappings using feedforward networks.
Neural Networks, 1993

Computability Properties of Low-dimensional Dynamical Systems.
Proceedings of the STACS 93, 1993

A Weak Version of the Blum, Shub & Smale model
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Relations between Models of Parallel Abstract Machines.
Proceedings of the Parallel Architectures and Their Efficient Use, 1992

Complexity Issues in Neural Network Computations.
Proceedings of the LATIN '92, 1992

1991
Meta-Level Interpretation of CLP(Lists).
Proceedings of the Constraint Logic Programming, 1991


  Loading...