Mémoire d'habilitation: Complexité et décidabilité pour les modèles de calcul algébriques et analogiques.
P. Koiran, N. Ressayre. Orbits of monomials and factorization into products of linear forms.
I. Garcia-Marco, P. Koiran and T. Pecatte. Polynomial equivalence problems for sums of affine powers. Conference version in Proc. ISSAC 2018.
P. Koiran. Root separation for trinomials. Accepted by Journal of Symbolic Computation.
I. Garcia-Marco, P. Koiran, T. Pecatte. On the linear independence of shifted powers. Journal of Complexity, 45:67-82, 2018.
I. Garcia-Marco, P. Koiran, T. Pecatte and S. Thomassé. On the complexity of partial derivatives, STACS 2017.
I. Garcia-Marco, P. Koiran and T. Pecatte. Reconstruction algorithms for sums of affine powers. Conference version in Proc. ISSAC 2017.
I. Garcia-Marco and P. Koiran. Lower bounds by Birkhoff interpolation. Journal of Complexity, 39:38-50, 2017.
I. Garcia-Marco, P. Koiran and S. Tavenas. Log-concavity and lower bounds for arithmetic circuits. MFCS 2015.
N. Kayal, P. Koiran, C. Saha and T. Pecatte. Lower bounds for sums of powers of low degree univariates. ICALP 2015.
P. Koiran, N. Portier, S. Tavenas. On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem. Discrete and Computational Geometry, 53(1):48-63, 2015.
P. Koiran, N. Portier, S. Tavenas, S. Thomassé. A τ-Conjecture for Newton Polygons. Foundations of Computational Mathematics, 15(1):185-197, 2015.
P. Koiran and A. Zouzias. Hidden cliques and the certification of the restricted isometry property. Preprint, 2012. Journal version in IEEE Transactions on Information Theory, 60(8):4999-5007, 2014.
P. Koiran and A. Zouzias. On the certification of the restricted isometry property. Preprint, 2011.
A. Chattopadhyay, B. Grenet, P. Koiran, N. Portier and Y. Strozecki. Factoring bivariate lacunary polynomials without heights. ISSAC 2013. Long version: Computing the multilinear factors of lacunary polynomials without heights, 2013 (submitted).
B. Grenet, P. Koiran, N. Portier and Y. Strozecki. The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent, FSTTCS 2011.
P. Koiran. Shallow circuits with high-powered inputs. In Proc. ICS 2011 (second Symposium on Innovations in Computer Science). Tsinghua University Press, Beijing.
B. Grenet, E. Kaltofen, P. Koiran and N. Portier. Symmetric determinantal representation of formulas and weakly skew circuits. In Randomization, Relaxation, and Complexity in Polynomial Equation Solving (Gurvits, pébay, Rojas, Thompson eds.). Contemporary Mathematics 556, AMS, 2011. Conference version: Symmetric determinantal representation of weakly skew circuits, STACS 2011.
P. Koiran. Arithmetic circuits: the chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012.
B. Grenet, P. Koiran and N. Portier. The Multivariate resultant is NP-hard in any characteristic, Journal of Complexity 29(2):142-157, 2013. Conference version in MFCS 2010 (35th International Symposium on Mathematical Foundations of Computer Science).
I. Briquel, P. Koiran and K. Meer. On the expressive power of CNF formulas of bounded tree- and clique-width. Discrete Applied Mathematics, 159(1):1-14, 2011. This 3-author paper is an extended version of a conference paper by the last two authors: On the expressive power of CNF formulas of bounded tree- and clique-width. In Proc. WG'08 (34th Workshop on Graph-Theoretic Concepts in Computer Science), pages 252-263, LNCS 5344, Springer, 2008.
P. Koiran and S. Perifel. Interpolation in Valiant's theory. Computational Complexity, 20(1):1-20, 2011.
P. Koiran and S. Perifel. A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. In Proc. CCC'09 (24th IEEE Conference on Computational Complexity).
P. Koiran, J. Landes, N. Portier and P. Yao. Adversary lower bounds for nonadaptive quantum algorithms. In Proc. Wollic 2008, pages 226-237, LNCS 5110. Long paper in Journal of Computer and System Sciences, 76(5):347-355, August 2010 (special issue on Wollic'08).
P. Koiran, V. Nesme and N. Portier. On the probabilistic query complexity of transitively symmetric problems. (October 2007 version).
P. Koiran, V. Nesme and N.
Portier. A quantum lower bound for the
query complexity of Simon's problem, ICALP 2005.
Long version: The quantum query complexity of Abelian hidden subgroup problems. Theoretical Computer Science, 380:115-126, 2007.
( LIP Research Report 2005-17).
H. Derksen, E. Jeandel and P.
Koiran. Quantum automata and
Journal of Symbolic Computation (special issue on the occasion of MEGA 2003), 39:3-4, pages 357-371, 2005. LIP Research Report 2003-39.
V. Blondel, E. Jeandel, P. Koiran and N. Portier. Decidable
and undecidable problems about quantum automata. LIP
Research Report 2003-34.
SIAM Journal on Computing, 34:6, pages 1464-1473, 2005.
E. Kaltofen and P. Koiran. Expressing a Fraction of Two Determinants as a Determinant. In Proc. ISSAC 2008, pages 141-146.
A. Chistov, H. Fournier, P. Koiran and S. Perifel. On the construction of a family of transversal subspaces over finite fields. Linear Algebra and its Applications, 429(2-3):589-600, 2008.
E. Kaltofen and P. Koiran. Finding Small Degree Factors of Multivariate Supersparse (Lacunary) Polynomials Over Algebraic Number Field. ISSAC'06.
E. Kaltofen and P. Koiran. On the complexity of factoring bivariate supersparse (lacunary) polynomials. ISSAC'05 (distinguished paper award).
P. Koiran, N. Portier and G.
Villard. A rank theorem for Vandermonde matrices. LIP
Research Report 2001-34.
You can also download an updated version of this report. Linear Algebra and its Applications, 378:99-107, 2004.
A. Chistov, H. Fournier, L. Gurvits and P. Koiran. Vandermonde Matrices, NP-Completeness, and Transversal Subspaces. LIP Research Report 2002-31. Foundations of Computational Mathematics, 3(4):421-427, 2003.
F. Cucker, P. Koiran and S. Smale. A polynomial-time
algorithm for diophantine equations in one variable.
LIP research report 1997-45. Journal of Symbolic Computation, 27:21-29, 1999.
These papers deal mostly with definability of geometric properties over the real and complex numbers (e.g. connectivity and irreducibility).
P. Koiran. The theory of
Liouville functions. LIP Research
Journal of Symbolic Logic, 68(2):353-365, 2003.
and N. Portier. Back-and-forth systems for generic curves and a
decision algorithm for the limit theory.
Annals of Pure and Applied Logic, 111:257-275, 2001. LIP Research Report 2000-29.
O. Chapuis, E. Hrushovski, P. Koiran et B. Poizat. La limite des théories de courbes génériques. Journal of Symbolic Logic.,67(1):24-34, 2002.
P. Koiran. On
defining irreducibility. preprint, 2000. Short version in
Comptes Rendus de l'Académie des Sciences ,
An older version of this paper can be found on the Los Alamos Archive.
Chapuis and P. Koiran. Definability of geometric properties in
algebraically closed fields.
LIP Research Report 98-32. Mathematical Logic Quarterly, 45(4): 533-550, 1999.
Dynamical systems viewed as computational devices.
V. Blondel, O. Bournez, P.
Koiran and J. Tsitsiklis. The
stability of saturated linear dynamical systems is
Journal of Computer and System Sciences, 62, pp. 442-462, 2001 (short version presented at STACS 2000).
V. Blondel, O. Bournez, P. Koiran, C. Papadimitriou and J.
Deciding stability and mortality of piecewise affine dynamical systems. LIP research report 1999-05.
Theoretical Computer Science. 255: (1-2), pp. 687-696, 2001.
P. Koiran and C. Moore. Closed-form analytic maps in one and two dimensions can simulate Turing machines. DIMACS Technical Report 96-25. Theoretical Computer Science, 210(1):217-223, 1999.
These papers deal mostly with algebraic models of computation, and
in particular with the real Turing machine of Blum, Shub and Smale. I
have been interested in problems with a model-theoretic flavor:
elimination of parameters from polynomial-time machines (click here
to see the corresponding reference on the top of the page) and in the
polynomial hierarchy, effective versions of
saturation and stability.
Transfer theorems relating boolean to algebraic complexity have been established for the problems
``P=NP?" and ``P=PSPACE?". More recently, I also became interested in Valiant's model of computation.
The complexity of a few "concrete" algebro-geometric problems is also studied, both from the algebraic and classical (bit cost) point of views: satisfiability of systems of polynomial equations, dimension of the solution set in the real case and in the complex case, dimensions of irreducible components.
I. Briquel and P. Koiran. A dichotomy theorem for polynomial evaluation. In Proc MFCS'09.
P. Koiran. A hitting set construction, with application to arithmetic circuit lower bounds. Preprint, 2009.
P. Koiran and S. Perifel. Diagonalization against Arithmetic Circuits (working paper).
P. Koiran and S. Perifel. VPSPACE and a transfer theorem over the complex field. In Proc. MFCS 2007, LNCS 4708, pages 359-370, 2007. P. Koiran and S. Perifel. The complexity of two problems on arithmetic circuits.Theoretical Computer Science, volume 389, pages 172-181, 2007.
U. Flarup, P. Koiran and L. Lyaudet. On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. Presented at ISAAC 2007 (conference paper). Presentation at FoCM 2008.
P. Koiran. Decision versus evaluation in algebraic complexity. This is an invited paper for MCU 2007 which surveys some of my recent work with Sylvain Périfel.
Finding a vector orthogonal to roughly half a collection of vectors. Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel and Stéphan Thomassé. Journal of Complexity 24(1):39-53, 2008. I recommend reading the following revised version of the paper, which includes an explicit description of the logspace algorithm.
Valiant's model and the cost of
LIP Research Report 2004-01. Computational Complexity, 13:131-146, 2004.
P. Koiran. Transfer theorems via sign conditions. LIP Research Report 2000-13. Information Processing Letters, 81:65-69, 2002.
P. Koiran. Circuits versus trees in algebraic complexity. STACS 2000, invited paper.
P. Koiran. The complexity of local dimensions for constructible sets. LIP research report 1999-05. Journal of Complexity 16:311-323, 2000.
H. Fournier and P. Koiran. Lower bounds are not easier over the reals: Inside PH. LIP Research Report 99-21. In Proc. ICALP 2000, LNCS 1853.
Fournier and P. Koiran. Are lower bounds easier over the reals?
In Proc. 30th ACM Symposium on Theory of Computing, pages 507--513, 1998. LIP Research Report 97-38.
Chapuis and P. Koiran. Saturation and
stability in the theory of computation over the reals.
Technical Report 1997/3, Institut Girard Desargues, Université Claude Bernard Lyon I, 1997.
Annals of Pure and Applied Logic., 99:1-49,1999.
The real dimension problem is NP_R complete. LIP
Research Report 97-36.
Journal of Complexity, 15:227-238, 1999.
Randomized and deterministic algorithms
for the dimension of algebraic varieties.
In Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 36-45, 1997.
Copyright 1997 © by IEEE, all rights reserved.
Elimination of parameters in the polynomial hierarchy.
LIP Research Report 98-15.
Theoretical Computer Science, 215:289-304, 1999.
F. Cucker, P. Koiran, and M. Matamala. Complexity and dimension. Information Processing Letters, 62:209-212, 1997. NeuroCOLT Technical Report 96-51.
P. Koiran. A weak version of the Blum, Shub & Smale model. Journal of Computer and System Sciences, 54:177-189, 1997. Preliminary version in Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993.
Approximating the volume of definable
sets. In Proc. 36th IEEE Symposium on Foundations of
Computer Science, pages 134-141, 1995.
Copyright 1995 Ž© by IEEE, all rights reserved.
F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther. On real Turing machines that toss coins. In Proc. 27th ACM Symposium on Theory of Computing, pages 335-342, 1995. NeuroCOLT Technical Report 95-18, and its erratum.
P. Koiran. Computing over the reals with addition and order. Theoretical Computer Science, 133(1):35-48, 1994. LIP Research Report 93-25.
M. Cosnard and P. Koiran. Relations between models of parallel abstract machines. In Proceedings of the Heinz Nixdorf Symposium,, Paderborn, November 1992, Lecture Notes in Computer Science, pages 37-46. Springer-Verlag, 1993.
These papers study the computational power of artificial neural networks and their learning complexity in the PAC (Probably Approximately Correct) framework. Some heuristics are also proposed and experimental results are reported.
P. Koiran and E. D. Sontag. Vapnik-Chervonenkis dimension of recurrent neural networks. In Proc. 3rd European Workshop on Computational Learning Theory, LNCS 1208, pages 223-237. Springer, 1997. DIMACS Technical Report 96-56.
P. Koiran and E. D. Sontag. Neural networks with quadratic VC dimension. Journal of Computer and System Sciences, 54:190-198, 1997. Preliminary version in Advances in Neural Information Processing Systems 8 (NIPS'95), MIT Press, 1996. NeuroCOLT Technical Report 95-44.
N. Dunkin, P. Koiran, and J. Shawe-Taylor. A new incremental learning technique. In Proc. 8th Italian Workshop on Neural Nets (WIRN'96), pages 112-118. Springer, 1997. NeuroCOLT Technical Report 97-14.
P. Koiran and J. Shawe-Taylor. Techniques in neural learning. NeuroCOLT Technical Report 95-36.
M. Cosnard, P. Koiran, and H. Paugam-Moisy. Complexity issues in neural network computations. In Proceedings of Latin'92, volume 583 of Lecture Notes in Computer Science, pages 530-545. Springer Verlag, 1992.
J. Cohen, V. Deschamps, and P. Koiran. Meta-level interpretation of CLP(Linear lists, Integers) enhanced by lazy evaluation and enumeration. In F. Benhamou and A. Colmerauer, editors, Constraint Logic Programming -- Selected Research, pages 457-481. The MIT Press, 1993.
Back to Pascal Koiran's home page