Recent papers

Older papers by topic:

Lower Bounds

Quantum Automata

Algebraic Computation

Model Theory

These papers deal mostly with definability of geometric properties over the real and complex numbers (e.g. connectivity and irreducibility).

Undecidability in Dynamical Systems

Dynamical systems viewed as computational devices.

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.

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.


Back to Pascal Koiran's home page