PUBLICATIONS

Mémoire d'habilitation: Complexité et décidabilité pour les modèles de calcul algébriques et analogiques.

Lower Bounds.

Quantum Automata.

Sparse polynomials.

Model Theory.

Undecidability in Dynamical Systems.

Algebraic Complexity.

Computational Learning Theory.

Miscellaneous.

PhD Thesis.

New papers!

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).
I. Briquel and P. Koiran. A dichotomy theorem for polynomial evaluation. To appear in Proc MFCS'09.
P. Koiran and S. Perifel. Diagonalization against Arithmetic Circuits (working paper).
I. Briquel, P. Koiran and K. Meer. On the expressive power of CNF formulas of bounded tree- and clique-width. 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, 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.
P. Koiran and S. Perifel. Interpolation in Valiant's theory.
P. Koiran, V. Nesme and N. Portier. On the probabilistic query complexity of transitively symmetric problems. (October 2007 version).

Lower Bounds

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.

Quantum Automata

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.

Algebraic Computation

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.

Model Theory

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.

Undecidability in Dynamical Systems

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.

Algebraic Complexity

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.

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.

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.

Computational Learning Theory

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.

Miscellaneous

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.

Back to Pascal Koiran's home page