Research

Algebraic complexity theory studies the complexity of fundamental computational problems within an algebraic framework of computation. This includes the design and analysis of efficient algorithms for algebraic problems, a topic belonging to computer algebra. Algebraic complexity adds to this the quest for lower complexity bounds, an enterprise genuine to theoretical computer science. The tools needed to establish such lower bounds cover a large spectrum of mathematics: ranging from combinatorics to representation theory, topology, and algebraic geometry.

A recent focus of the research group is on geometric complexity theory, which is an attempt to proving complexity lower bounds based on tools from geometry and representation theory. 

Another current focus of the research group is on the probabilistic analysis of numerical algorithms and condition numbers. We have contributed to the solution of Smale's 17th problem regarding the complexity of solving systems of polynomial equations numerically. We have also contributed to the theory of condition numbers in convex optimization.