Theory Colloquium
The Theory Colloquium is jointly organized by the Faculty of Computer Science and the Max Planck Institute for Security and Privacy. The talks in the series highlight exciting areas of current theoretical computer science research; familoarity with the topics is not assumed.
The inaugural talk will be on June 15, 2022. All interested parties are cordially invited!
Speaker: Prof. Dr. Bürgisser (TU Berlin)
Title: Complexity of computing complex zeros of structured polynomial systems
Date: Wednesday, June 15, 12-1 pm
Place: MC. 1.84 (former bulding VC, access via the open space or the southern elevator), who can not be on site, can follow the lecture via zoom .
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.