Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPascal Koiran
Person information
- affiliation: ENS Lyon, France
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[j55]Pascal Koiran, Subhayan Saha:
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond. Comput. Complex. 32(2): 8 (2023)- [c43]Pascal Koiran, Subhayan Saha:
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision. CIAC 2023: 308-322 - 2022
- [c42]Pascal Koiran, Subhayan Saha:
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. FSTTCS 2022: 24:1-24:17 - [i39]Pascal Koiran, Subhayan Saha:
Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision. CoRR abs/2211.07407 (2022) - 2021
- [j54]Arkadev Chattopadhyay, Bruno Grenet
, Pascal Koiran, Natacha Portier, Yann Strozecki:
Computing the multilinear factors of lacunary polynomials without heights. J. Symb. Comput. 104: 183-206 (2021) - [j53]Pascal Koiran, Mateusz Skomra:
Derandomization and absolute reconstruction for sums of powers of linear forms. Theor. Comput. Sci. 887: 63-84 (2021) - [i38]Pascal Koiran, Subhayan Saha:
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. CoRR abs/2110.05305 (2021) - 2020
- [j52]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte:
Reconstruction algorithms for sums of affine powers. J. Symb. Comput. 98: 284-318 (2020) - [i37]Pascal Koiran:
On tensor rank and commuting matrices. CoRR abs/2006.02374 (2020)
2010 – 2019
- 2019
- [j51]Pascal Koiran:
Root separation for trinomials. J. Symb. Comput. 95: 151-161 (2019) - [i36]Pascal Koiran, Mateusz Skomra:
Intersection multiplicity of a sparse curve and a low-degree curve. CoRR abs/1904.00702 (2019) - [i35]Pascal Koiran:
Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective. CoRR abs/1905.05094 (2019) - [i34]Pascal Koiran, Mateusz Skomra:
Derandomization and absolute reconstruction for sums of powers of linear forms. CoRR abs/1912.02021 (2019) - 2018
- [j50]Pascal Koiran, Timothée Pecatte, Ignacio García-Marco:
On the linear independence of shifted powers. J. Complex. 45: 67-82 (2018) - [c41]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte:
Polynomial Equivalence Problems for Sum of Affine Powers. ISSAC 2018: 303-310 - [i33]Pascal Koiran, Nicolas Ressayre:
Orbits of monomials and factorization into products of linear forms. CoRR abs/1807.03663 (2018) - 2017
- [j49]Ignacio García-Marco, Pascal Koiran:
Lower bounds by Birkhoff interpolation. J. Complex. 39: 38-50 (2017) - [c40]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte:
Reconstruction Algorithms for Sums of Affine Powers. ISSAC 2017: 317-324 - [c39]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé:
On the Complexity of Partial Derivatives. STACS 2017: 37:1-37:13 - [i32]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte:
On the linear independence of shifted powers. CoRR abs/1705.03842 (2017) - [i31]Pascal Koiran:
Root Separation for Trinomials. CoRR abs/1709.03294 (2017) - 2016
- [i30]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte:
Reconstruction Algorithms for Sums of Affine Powers. CoRR abs/1607.05420 (2016) - [i29]Ignacio García-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé:
On the complexity of partial derivatives. CoRR abs/1607.05494 (2016) - 2015
- [j48]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): 48-63 (2015) - [j47]Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé:
A $$\tau $$ τ -Conjecture for Newton Polygons. Found. Comput. Math. 15(1): 185-197 (2015) - [j46]Pascal Koiran, Natacha Portier, Sébastien Tavenas:
A Wronskian approach to the real τ-conjecture. J. Symb. Comput. 68: 195-214 (2015) - [c38]Neeraj Kayal, Pascal Koiran, Timothée Pecatte, Chandan Saha:
Lower Bounds for Sums of Powers of Low Degree Univariates. ICALP (1) 2015: 810-821 - [c37]Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas:
Log-Concavity and Lower Bounds for Arithmetic Circuits. MFCS (2) 2015: 361-371 - [i28]Ignacio García-Marco, Pascal Koiran, Sébastien Tavenas:
Log-concavity and lower bounds for arithmetic circuits. CoRR abs/1503.07705 (2015) - [i27]Ignacio García-Marco, Pascal Koiran:
Lower Bounds by Birkhoff Interpolation. CoRR abs/1507.02015 (2015) - 2014
- [j45]Pascal Koiran, Anastasios Zouzias:
Hidden Cliques and the Certification of the Restricted Isometry Property. IEEE Trans. Inf. Theory 60(8): 4999-5006 (2014) - 2013
- [j44]Bruno Grenet, Pascal Koiran, Natacha Portier:
On the complexity of the multivariate resultant. J. Complex. 29(2): 142-157 (2013) - [c36]Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki:
Factoring bivariate lacunary polynomials without heights. ISSAC 2013: 141-148 - [i26]Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé:
A tau-conjecture for Newton polygons. CoRR abs/1308.2286 (2013) - [i25]Pascal Koiran, Natacha Portier, J. Maurice Rojas:
Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent. CoRR abs/1309.0486 (2013) - [i24]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 abs/1310.2447 (2013) - [i23]Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki:
Computing the multilinear factors of lacunary polynomials without heights. CoRR abs/1311.5694 (2013) - [i22]Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran:
Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 3(1): 47-66 (2013) - 2012
- [j43]Pascal Koiran:
Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci. 448: 56-65 (2012) - [c35]Pascal Koiran:
Upper bounds on real roots and lower bounds for the permanent. ISSAC 2012: 8 - [i21]Pascal Koiran, Natacha Portier, Sébastien Tavenas:
A Wronskian Approach to the real τ-conjecture. CoRR abs/1205.1015 (2012) - [i20]Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki:
Factoring bivariate lacunary polynomials without heights. CoRR abs/1206.4224 (2012) - [i19]Bruno Grenet, Pascal Koiran, Natacha Portier:
On the Complexity of the Multivariate Resultant. CoRR abs/1210.1451 (2012) - [i18]Pascal Koiran, Anastasios Zouzias:
Hidden cliques and the certification of the restricted isometry property. CoRR abs/1211.0665 (2012) - 2011
- [j42]Pascal Koiran, Sylvain Perifel:
Interpolation in Valiant's Theory. Comput. Complex. 20(1): 1-20 (2011) - [j41]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): 1-14 (2011) - [c34]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: 127-139 - [c33]Pascal Koiran:
Shallow circuits with high-powered inputs. ICS 2011: 309-320 - [c32]Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier:
Symmetric Determinantal Representation of Weakly-Skew Circuits. STACS 2011: 543-554 - [i17]Pascal Koiran, Anastasios Zouzias:
On the Certification of the Restricted Isometry Property. CoRR abs/1103.4984 (2011) - [i16]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 abs/1107.1434 (2011) - 2010
- [j40]Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao:
Adversary lower bounds for nonadaptive quantum algorithms. J. Comput. Syst. Sci. 76(5): 347-355 (2010) - [c31]Bruno Grenet, Pascal Koiran, Natacha Portier:
The Multivariate Resultant Is NP-hard in Any Characteristic. MFCS 2010: 477-488 - [i15]Pascal Koiran:
Shallow Circuits with High-Powered Inputs. CoRR abs/1004.4960 (2010) - [i14]Pascal Koiran:
Arithmetic circuits: the chasm at depth four gets wider. CoRR abs/1006.4700 (2010) - [i13]Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, Natacha Portier:
Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits. CoRR abs/1007.3804 (2010)
2000 – 2009
- 2009
- [j39]Pascal Koiran, Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals. Comput. Complex. 18(4): 551-575 (2009) - [j38]Pascal Koiran, Sylvain Perifel:
VPSPACE and a transfer theorem over the complex field. Theor. Comput. Sci. 410(50): 5244-5251 (2009) - [c30]Pascal Koiran, Sylvain Perifel:
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. CCC 2009: 35-40 - [c29]Irénée Briquel, Pascal Koiran:
A Dichotomy Theorem for Polynomial Evaluation. MFCS 2009: 187-198 - [i12]Pascal Koiran, Sylvain Perifel:
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. CoRR abs/0902.1866 (2009) - [i11]Irénée Briquel, Pascal Koiran:
Toward a Dichotomy Theorem for Polynomial Evaluation. CoRR abs/0902.2300 (2009) - [i10]Pascal Koiran:
A hitting set construction, with application to arithmetic circuit lower bounds. CoRR abs/0907.5575 (2009) - [i9]Bruno Grenet, Pascal Koiran, Natacha Portier:
The multivariate resultant lies between NP and AM. CoRR abs/0912.2607 (2009) - 2008
- [j37]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): 39-53 (2008) - [c28]Erich L. Kaltofen, Pascal Koiran:
Expressing a fraction of two determinants as a determinant. ISSAC 2008: 141-146 - [c27]Pascal Koiran, Klaus Meer:
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width. WG 2008: 252-263 - [c26]Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao:
Adversary Lower Bounds for Nonadaptive Quantum Algorithms. WoLLIC 2008: 226-237 - [i8]Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao:
Adversary lower bounds for nonadaptive quantum algorithms. CoRR abs/0804.1440 (2008) - 2007
- [j36]Pascal Koiran, Vincent Nesme, Natacha Portier:
The quantum query complexity of the abelian hidden subgroup problem. Theor. Comput. Sci. 380(1-2): 115-126 (2007) - [j35]Pascal Koiran, Sylvain Perifel:
The complexity of two problems on arithmetic circuits. Theor. Comput. Sci. 389(1-2): 172-181 (2007) - [c25]Uffe Flarup, Pascal Koiran, Laurent Lyaudet:
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. ISAAC 2007: 124-136 - [c24]Pascal Koiran:
Decision Versus Evaluation in Algebraic Complexity. MCU 2007: 80-89 - [c23]Pascal Koiran, Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Complex Field. MFCS 2007: 359-370 - [c22]Pascal Koiran, Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals. STACS 2007: 417-428 - [i7]Laurent Lyaudet, Pascal Koiran, Uffe Flarup:
On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. CoRR abs/0705.3751 (2007) - [i6]Pascal Koiran, Sylvain Perifel:
VPSPACE and a transfer theorem over the complex field. CoRR abs/0706.1477 (2007) - [i5]Pascal Koiran, Sylvain Perifel:
Interpolation in Valiant's theory. CoRR abs/0710.0360 (2007) - 2006
- [c21]Erich L. Kaltofen, Pascal Koiran:
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. ISSAC 2006: 162-168 - [c20]Pascal Koiran, Sylvain Perifel:
Valiant's Model: From Exponential Sums to Exponential Products. MFCS 2006: 596-607 - [i4]Pascal Koiran, Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals. CoRR abs/cs/0610009 (2006) - 2005
- [j34]Pascal Koiran:
Valiant's model and the cost of computing integers. Comput. Complex. 13(3-4): 131-146 (2005) - [j33]Askold Khovanskii, Pascal Koiran, Teresa Krick, Gregorio Malajovich, Joseph F. Traub:
Guest editors' preface. J. Complex. 21(1): 4- (2005) - [j32]Harm Derksen, Emmanuel Jeandel, Pascal Koiran:
Quantum automata and algebraic groups. J. Symb. Comput. 39(3-4): 357-371 (2005) - [j31]Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier:
Decidable and Undecidable Problems about Quantum Automata. SIAM J. Comput. 34(6): 1464-1473 (2005) - [c19]Pascal Koiran, Vincent Nesme, Natacha Portier:
A Quantum Lower Bound for the Query Complexity of Simon's Problem. ICALP 2005: 1287-1298 - [c18]Erich L. Kaltofen, Pascal Koiran:
On the complexity of factoring bivariate supersparse (Lacunary) polynomials. ISSAC 2005: 208-215 - [i3]Pascal Koiran, Vincent Nesme, Natacha Portier:
A quantum lower bound for the query complexity of Simon's problem. CoRR abs/quant-ph/0501060 (2005) - 2004
- [i2]Pascal Koiran:
Valiant's model and the cost of computing integers. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j30]Alexander L. Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran:
Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. Found. Comput. Math. 3(4): 421-427 (2003) - [j29]Pascal Koiran:
The theory of Liouville functions. J. Symb. Log. 68(2): 353-365 (2003) - 2002
- [j28]Pascal Koiran:
Transfer theorems via sign conditions. Inf. Process. Lett. 81(2): 65-69 (2002) - [j27]Olivier Chapuis, Ehud Hrushovski, Pascal Koiran, Bruno Poizat:
La Limite des Theories de Courbes Generiques. J. Symb. Log. 67(1): 24-34 (2002) - 2001
- [j26]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): 257-275 (2001) - [j25]Pascal Koiran:
The topological entropy of iterated piecewise affine maps is uncomputable. Discret. Math. Theor. Comput. Sci. 4(2): 351-356 (2001) - [j24]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): 442-462 (2001) - [j23]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): 687-696 (2001) - 2000
- [j22]Pascal Koiran:
The Complexity of Local Dimensions for Constructible Sets. J. Complex. 16(1): 311-323 (2000) - [j21]Jean-Pierre Dedieu, Pascal Koiran:
Guest Editors' Preface. J. Complex. 16(3): 528 (2000) - [c17]Hervé Fournier, Pascal Koiran:
Lower Bounds Are Not Easier over the Reals: Inside PH. ICALP 2000: 832-843 - [c16]Pascal Koiran:
Circuits versus Trees in Algebraic Complexity. STACS 2000: 35-52 - [c15]Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis:
The Stability of Saturated Linear Dynamical Systems Is Undecidable. STACS 2000: 479-490
1990 – 1999
- 1999
- [j20]Olivier Chapuis, Pascal Koiran:
Saturation and Stability in the Theory of Computation over the Reals. Ann. Pure Appl. Log. 99(1-3): 1-49 (1999) - [j19]Pascal Koiran:
The Real Dimension Problem Is NPR-Complete. J. Complex. 15(2): 227-238 (1999) - [j18]Felipe Cucker, Pascal Koiran, Steve Smale:
A Polynomial Time Algorithm for Diophantine Equations in One Variable. J. Symb. Comput. 27(1): 21-29 (1999) - [j17]Olivier Chapuis, Pascal Koiran:
Definability of Geometric Properties in Algebraically Closed Fields. Math. Log. Q. 45: 533-550 (1999) - [j16]Pascal Koiran, Cristopher Moore:
Closed-for Analytic Maps in One and Two Dimensions can Simulate Universal Turing Machines. Theor. Comput. Sci. 210(1): 217-223 (1999) - [j15]Pascal Koiran:
Elimination of Parameters in the Polynomial Hierarchy. Theor. Comput. Sci. 215(1-2): 289-304 (1999) - 1998
- [j14]Pascal Koiran, Eduardo D. Sontag:
Vapnik-Chervonenkis Dimension of Recurrent Neural Networks. Discret. Appl. Math. 86(1): 63-79 (1998) - [c14]Hervé Fournier, Pascal Koiran:
Are Lower Bounds Easier over the Reals? STOC 1998: 507-513 - 1997
- [j13]Felipe Cucker, Pascal Koiran, Martín Matamala:
Complexity and Dimension. Inf. Process. Lett. 62(4): 209-212 (1997) - [j12]Pascal Koiran:
Elimination of Constants from Machines over Algebraically Closed Fields. J. Complex. 13(1): 65-82 (1997) - [j11]Pascal Koiran:
A Weak Version of the Blum, Shub, and Smale Model. J. Comput. Syst. Sci. 54(1): 177-189 (1997) - [j10]Pascal Koiran, Eduardo D. Sontag:
Neural Networks with Quadratic VC Dimension. J. Comput. Syst. Sci. 54(1): 190-198 (1997) - [j9]Leonid Gurvits, Pascal Koiran:
Approximation and Learning of Convex Superpositions. J. Comput. Syst. Sci. 55(1): 161-170 (1997) - [c13]Pascal Koiran, Eduardo D. Sontag:
Vapnik-Chervonenkis Dimension of Recurrent Neural Networks. EuroCOLT 1997: 223-237 - [c12]Pascal Koiran:
Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. FOCS 1997: 36-45 - 1996
- [j8]Pascal Koiran:
Hilbert's Nullstellensatz Is in the Polynomial Hierarchy. J. Complex. 12(4): 273-286 (1996) - [j7]Pascal Koiran:
A Family of Universal Recurrent Networks. Theor. Comput. Sci. 168(2): 473-480 (1996) - [c11]Pascal Koiran:
VC Dimension in Circuit Complexity. CCC 1996: 81-85 - 1995
- [j6]Felipe Cucker, Pascal Koiran:
Computing over the Reals with Addition and Order: Higher Complexity Classes. J. Complex. 11(3): 358-376 (1995) - [c10]Leonid Gurvits, Pascal Koiran:
Approximation and learning of convex superpositions. EuroCOLT 1995: 222-236 - [c9]Pascal Koiran:
Approximating the Volume of Definable Sets. FOCS 1995: 134-141 - [c8]Pascal Koiran, Eduardo D. Sontag:
Neural Networks with Quadratic VC Dimension. NIPS 1995: 197-203 - [c7]Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther:
On real Turing machines that toss coins. STOC 1995: 335-342 - [i1]