Computational complexity is concerned with the amount of resources that are necessary and sufficient to solve a given problem. Classically, the complexity of discrete (Boolean) objects is studied. Often, the most promising way to argue about these Boolean problems is by establishing a connection to an algebraic setting that is easier to understand. Some of the deepest and most powerful results rely on algebraic proof techniques, like the Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test.

Using algebraic circuits, that is, circuits with algebraic operations like addition and multiplication instead of Boolean operations, as the underlying model of computation led to the field of algebraic complexity. Algebraic complexity tries to understand the complexity of algebraic objects, like multivariate polynomials, tensor, etc. Many Boolean problems have algebraic counterparts. The famous P versus NP problem can be phrased as the question whether certain polynomials, like the permanent, cannot be computed by polynomial-size algebraic circuits. Since algebraic objects have more structure than Boolean ones, we hope that it is easier to make progress in the algebraic world.

This event brings together established researchers and young scientists to study algebraic, but also other aspects of computational complexity. Besides regular talks, there will be tutorial style talks, which give a gentle introduction to a certain topic. There will be ample time for individual discussions and many opportunities for small groups to work on a concrete problem.

Creative Commons BY 3.0 DE

Markus Bläser and Jacobo Torán