TU Berlin

Fachgebiet Algorithmische AlgebraBook Chapters

Page Content

to Navigation

There is no English translation for this web page.

Book Chapters

Lower Bounds and Real Algebraic Geometry
Citation key B-2003-Lower-Bounds-and-Real-Algebraic-Geometry
Author Peter Bürgisser
Title of Book Algorithmic and Quantitative Real Algebraic Geometry
Pages 35-54
Year 2003
Volume 60
Note Erratum: http://www.math.tu-berlin.de/algebra/work/erratum.pdf
Editor Saugata Basu and Laureano Gonzalez-Vega
Publisher AMS
Abstract Many relevant problems in symbolic computation and computational geometry can be formalized as semi-algebraic computation or decision problems, to be solved by means of algebraic computation trees. It is a general paradigm that a complicated geometrical, topological, or combinatorial structure of a problem should result in high computational complexity. This survey outlines some of the ideas leading to lower bounds in terms of degree, Betti numbers, and number of faces of an arrangement or a polyhedron, emphasizing the role of real algebraic geometry in this endeavour. The impact of randomization on decision complexity is briefly discussed.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe