Computational complexity, topology, and singularities

• Applicant: Professor Dr. Peter Bürgisser
• Subject Area: Mathematics
• Term: from 2002 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5379865

• Final Report Year: 2007

Final Report Abstract

Die Menge der komplexen Lösungen eines unterbestimmten polynomialen Gleichungssystems ist im allgemeinen unendlich, kann jedoch in ihrer Gesamtheit durch gewisse ganzzahlige Grössen grob beschrieben werden. Neben der Dimension der Lösungsmenge sind solche topologische Grössen z.B. die Anzahl Zusammenhangskomponenten oder deren Bettizahlen, welche den Zusammenhang in einem höherdimensionalen Sinn messen. Die wichtigste topologische Invariante ist die Eulercharakteristik. Relevante algebraisch-geometrische Grossen sind vor allem der Grad und das Hilbertpolynom. Es ist bekannt, dass diese Grössen in gewissen Fällen untere Komplexitätsschranken für algebraische Berechnungsprobleme liefern (Strassen). Die ursprüngliche Zielsetzung des Projektes war es, die Tragweite dieses Ansatzes zum Beweis unterer Komplexitätsschranken systematisch auszuloten. Im Zuge einer Neuausrichtung des Projekts rückte das Studium der Berechnungskomplexität dieser Grössen selbst in den Mittelpunkt. Das Hauptergebnis ist die Entwicklung einer Theorie, in deren Rahmen eine Klassifikation der inhärenten Berechnungskomplexität der obengenannten (und weiterer) Grossen ermöglicht wird. Ein wesentlicher Aspekt dieser Theorie ist die Übertragung von bekannten Konzepten zur Erfassung der Komplexität von Zählproblemen (Valiant) in den Kontext der algebraischen Geometrie. Dies geschieht durch eine Weiterentwicklung der algebraischen Theorie der NP-Vollständigkeit im Sinne von Blum, Shub und Smale. Die Ergebnisse lassen sich als Polynomialzeit-Reduktionen zwischen verschiedenen Problemen formulieren. Bei deren Entwurf spielen Methoden der enumerativen Geometrie, Morsetheorie und Singularitäten eine Rolle. Es besteht die Hoffnung, dass die neuen Einsichten zu Algorithmen führen werden, welche nicht nur theoretisch, sondern auch praktisch schneller sind, als z.B. auf Gröbnerbasen beruhende Verfahren.

Publications

• Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. Proc. 43rd Annual IEEE Symp. on Foundations of Computer Science (FOCS 2002), Vancouver, pp. 658-668, 2002
  Peter Bürgisser, M. Lotz
  
• Counting Complexity Classes for Numeric Computations I: Semilinear Sets. SIAM Journal on Computing 33(1): 227-260, 2003
  Peter Bürgisser, F. Cucker
  
• Counting Complexity Classes over the Reals. I: The Additive Case. Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Kyoto. Springer Lecture Notes in Computer Science 2906, pp. 625-634, Springer, 2003
  Peter Bürgisser, F. Cucker
  
• Lower Bounds and Real Algebraic Geometry. In: Algorithmic and Quantitative Real Algebraic Geometry, Saugata Basu, Laureano Gonzalez-Vega (eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 60, pp. 35-54, American Mathematical Society, 2003
  Peter Bürgisser
  
• Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets. Proc. 36th Annual ACM Symposium on Theory of Computing (STOC 2004), Chicago, pp. 475-485, 2004
  Peter Bürgisser, F. Cucker
  
• Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. Journal of the ACM 51(3): 464-482, 2004
  Peter Bürgisser, M. Lotz
  
• The Complexity to Compute the Euler Characteristic of Complex Varieties . Comptes rendus de l'Academic des sciences Paris, Ser. I 339, 371-376, 2004
  Peter Bürgisser, F. Cucker and M. Lotz
  
• Variations by complexity theorists on three themes of Euler, Bezout, Betti, and Poincare. In: Complexity of computations and proofs, Jan Krajicek (ed.), Quaderni di Matematica, volume 13, pp. 73-151, 2004
  Peter Bürgisser, F. Cucker
  
• Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets. Foundations of Computational Mathematics 5(4), 351- 387, 2005
  Peter Bürgisser, F. Cucker and M. Lotz
  
• The complexity of semilinear problems in succinct representation. Proc. of 15th International Symposium on Fundamentals of Computation Theory (FCT '05), Lecture Notes in Computer Science 3623, pp. 479-490, Springer, 2005
  Peter Bürgisser, F. Cucker and P. de Naurois
  
• Average volume, curvatures, and Euler characteristic of random real algebraic varieties. 2006
  Peter Bürgisser
  
• Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets. Journal of Complexity 22(2), 147-191, 2006
  Peter Bürgisser, F. Cucker
  
• On the Complexity of Numerical Analysis. Proc. of 21st Ann. IEEE Conference on Computational Complexity, pp. 331-339, 2006
  Peter Bürgisser, E. Allender, J. Kjeldgaard-Pedersen, and P. Miltersen
  
• The complexity of semilinear problems in succinct representation. Computational Complexity 15(3): 197-235 (2006)
  Peter Bürgisser, F. Cucker and P. de Naurois
  
• On defining integers in the counting hierarchy and proving arithmetic circuit lower bounds. Proc. of 24th International Symposium on Theoretical Aspects of Computer Science (STAGS 2007), Lecture Notes in Computer Science 4393, pp. 133-144. Springer, 2007
  Peter Bürgisser
  
• The complexity of computing the Hubert polynomial of smooth complex projective varieties. Foundations of Computational Mathematics 7(1): 51-86 (2007)
  Peter Bürgisser, M. Lotz