TU Berlin

Fachgebiet Algorithmische AlgebraBook Chapters

Inhalt des Dokuments

zur Navigation

Book Chapters

Lower Bounds and Real Algebraic Geometry
Zitatschlüssel B-2003-Lower-Bounds-and-Real-Algebraic-Geometry
Autor Peter Bürgisser
Buchtitel Algorithmic and Quantitative Real Algebraic Geometry
Seiten 35-54
Jahr 2003
Jahrgang 60
Notiz Erratum: http://www.math.tu-berlin.de/algebra/work/erratum.pdf
Herausgeber Saugata Basu and Laureano Gonzalez-Vega
Verlag AMS
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe