View abstract

Session II.3 - Real-Number Complexity

Thursday, June 15, 14:00 ~ 14:30

New developments on the existential theory of the reals.

Till Miltzow

Utrecht University, Netherlands   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

In Computational Complexity Theory, we categorize algorithmic problems by their difficulty level. Those levels have names like P, PSPACE, NP, PPAD, #P, ER, and many more. They are usually referred to as complexity classes.

One such class (the existential theory of the reals) is denoted by ER and encapsulates all problems that are equally difficult to feasibility. In feasibility, we want to find an x∈R^n such that p(x)=0. Here, p is a polynomial with integer coefficients. Interestingly, it turns out that many relevant problems in Computer Science are equivalent to this core problem. Examples are geometric packing, training neural networks, or finding Nash Equilibria.

To illustrate the implications let us take the example of packing geometric objects, by rotation and translation. Clearly, this problem can be solved by solving polynomial equations. Recent results state that it is not possible to do so without solving polynomial equations. (Or at least methods that are powerful enough to solve polynomial equations.) This explains at least partially, the lack of algorithmic progress on geometric packing, compared to other algorithmic problems like the traveling salesperson problem. We want to note that practical difficulty might be easier, as real-life instances might have more structure than adversary worst-case examples. Still, complexity classes give an important indication of practical difficulty.

In this talk, we will give highlights on the complexity class ER from the last decade.

View abstract PDF