All reports by Author Peter Bürgisser:

__
TR05-138
| 22nd November 2005
__

Peter Bürgisser, Felipe Cucker#### Exotic quantifiers, complexity classes, and complete problems

__
TR05-037
| 8th April 2005
__

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen#### On the Complexity of Numerical Analysis

Revisions: 1
,
Comments: 1

Peter Bürgisser, Felipe Cucker

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

We study two quite different approaches to understanding the complexity

of fundamental problems in numerical analysis. We show that both hinge

on the question of understanding the complexity of the following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>