Theory Colloquium
Das Theory Colloquium wird gemeinsam von der Fakultät für Informatik und dem Max Planck Institut für Sicherheit und Privatsphäre organisiert. Die Vorträge der Reihe beleuchten spannende Gebiete der aktuellen theoretischen Informatikforschung, Vorkenntnisse zu den Themen werden nicht vorausgesetzt.
Den Auftaktveranstaltung ist am 15. Juni 2022. Alle Interessierten sind herzlich eingeladen!
Sprecher: Prof. Dr. Bürgisser (TU Berlin)
Titel: Complexity of computing complex zeros of structured polynomial systems
Datum: Mittwoch, 15. Juni, 12-13 Uhr
Ort: MC. 1.84 (ehemaliges Gebäude VC, Zugang über den Open Space oder den südlichen Fahrstuhl), wer nicht vor Ort sein kann, kann den Vortrag per Zoom verfolgen
Abstract:
Can we solve polynomial systems in polynomial time? This question received different answers in different contexts. The NP-hardness of deciding the feasibility of a general polynomial system does not preclude efficient algorithms for computing complex zeros of polynomial systems with as many equations as variables, on which the feasibility is granted under genericity hypotheses. Smale’s 17th problem is a clear-cut formulation of the problem in a numerical setting. We report on recent progress that gives a positive answer to a refinement of Smale’s question for structured systems. Joint work with Felipe Cucker and Pierre Lairez.