Back
to Pascal Koiran's home page
Mémoire d'habilitation: Complexité et décidabilité pour les modèles de calcul algébriques et analogiques.
P. Koiran and A. Zouzias. On the certification of the restricted isometry property. Preprint, 2011.
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. Preprint, 2010. To appear in Theoretical Computer Science.
B. Grenet, P. Koiran and N. Portier. The Multivariate resultant is NP-hard in any characteristic, 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).
P. Koiran. VC dimension in circuit complexity. In Proc. 11th IEEE Conference on Computational Complexity, pages 81-85, 1996. ECCC technical report 95-051.
H. Derksen, E. Jeandel and P.
Koiran. Quantum automata and
algebraic groups.
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 Report
2002-13.
Journal of Symbolic Logic,
68(2):353-365, 2003.
P. Koiran. The limit theory of
generic polynomials. LIP Research
Report 2001-35.
See also LIP
Research Report 2001-34. To appear in Proc. Logic
Colloquium 2001.
P. Koiran 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 ,
330:529-532, 2000.
An older version of this paper can be found on
the Los Alamos Archive.
O.
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.
P. Koiran. The topological entropy of iterated piecewise affine maps is uncomputable. DMTCS, 4(2):351-356, 2001. LIP research report 2000-36.
V. Blondel, O. Bournez, P. Koiran
and J. Tsitsiklis. The stability of
saturated linear dynamical systems is undecidable.
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.
Tsitsiklis.
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.
P. Koiran. A family of universal recurrent networks. Theoretical Computer Science, 168(2):473-480, 1996.
P. Koiran, M. Cosnard, and M. Garzon. Computability with low-dimensional dynamical systems. Theoretical Computer Science, 132:113-128, 1994.
P. Koiran. Dynamics of discrete time, continuous state Hopfield networks. Neural Computation, 6:459-468, 1994.
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.
P. Koiran and S. Perifel. VPSPACE and a transfer theorem over the reals. Appeared in Proc. STACS 2007. Long version to appear in Computational Complexity.
Finding a vector orthogonal to roughly half a collection of vectors. Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel and Stéphan Thomassé. Accepted for publication in Journal of Complexity. I recommend reading the following revised version of the paper, which includes an explicit description of the logspace algorithm.
P. Koiran.
Valiant's model and the cost of
computing integers.
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.
H.
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.
O.
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.
P. Koiran. The
real dimension problem is NP_R complete. LIP
Research Report 97-36.
Journal of Complexity,
15:227-238, 1999.
P. Koiran.
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.
P. Koiran.
Elimination of parameters in the polynomial hierarchy.
LIP Research Report 98-15.
Theoretical
Computer Science, 215:289-304, 1999.
P. Koiran. Elimination of constants from machines over algebraically closed fields. Journal of Complexity , 13(1):65-82, 1997. DIMACS Technical Report 96-24 and its erratum.
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.
P. Koiran. Hilbert's Nullstellensatz is in the polynomial hierarchy. Journal of Complexity, 12(4):273-286, 1996. There is a longer paper ( DIMACS Technical Report 96-27) and an erratum.
P. Koiran.
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.
F. Cucker and P. Koiran. Computing over the reals with addition and order: Higher complexity classes. Journal of Complexity, 11:358-376, 1995.
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.
L. Gurvits and P. Koiran. Approximation and learning of convex superpositions. Journal of Computer and System Sciences, 55(1):161--170, 1997.
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.
P. Koiran. Efficient learning of continuous neural networks. In Proc. 7th ACM Conference on Computational Learning Theory, pages 348-355, 1994.
M. Cosnard, P. Koiran, and H. Paugam-Moisy. A step towards the frontier between one-hidden-layer and two-hidden layer neural networks. In Proc. IJCNN Nagoya, volumeŽ 3, pages 2292-2295, 1993.
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.
M. Cosnard, P. Koiran, and H. Paugam-Moisy. Bounds on the number of units for computing arbitrary dichotomies by multilayer perceptrons. Journal of Complexity, 10(1), March 1994.
P. Koiran. On the complexity of approximating mappings using feedforward networks. Neural Networks, 6:649-653, 1993.
P. Koiran. Function approximation using a partition of the input space. In Proc. IJCNN Baltimore, volume I, pages 883-887, 1992.
P. Koiran. Approximation of mappings and application to translation invariant networks. In Proc. IJCNN Singapore, pages 2292-2298, 1991.
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.
B. Durand, P. Koiran, and C. Mazenc. Writing a compiler with Eiffel. In Proc. 5th International Eiffel Conference, 1990.