Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Peter Bürgisser:

TR05-138 | 22nd November 2005
Peter Bürgisser, Felipe Cucker

Exotic quantifiers, complexity classes, and complete problems

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint