TU Berlin

Fachgebiet Algorithmische AlgebraBook Chapters

Page Content

to Navigation

There is no English translation for this web page.

Book Chapters

Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré
Citation key BC-2005-Variations-by-complexity-theorists-on-three-themes-of-Euler-Bezout-Betti-and-Poincare
Author Peter Bürgisser and Felipe Cucker
Title of Book Complexity of computations and proofs
Pages 73-152
Year 2005
Volume 13
Editor Jan Krajicek
Publisher Quaderni di Matematica
Abstract This paper surveys some connections between geometry and complexity. A main role is played by some quantities - degree, Euler characteristic, Betti numbers - associated to algebraic or semialgebraic sets. This role is twofold. On the one hand, lower bounds on the deterministic time (sequential and parallel) necessary to decide a set S are established as functions of these quantities associated to S. The optimality of some algorithms is obtained as a consequence. On the other hand, the computation of these quantities gives rise to problems which turn out to be hard (or complete) in different complexity classes. These two kind of results thus turn the quantities above into measures of complexity in two quite different ways.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe