https://www.dagstuhl.de/20385

September 13 – 18 , 2020, Event 20385

Algebraic and Other Aspects of Complexity Theory

Organizers

Markus Bläser (Universität des Saarlandes – Saarbrücken, DE)
Jacobo Torán (Universität Ulm, DE)

For support, please contact

Heike Clemens

Documents

Event Schedule (Upload here)

(Use personal credentials as created in DOOR to log in)

Motivation

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Markus Bläser and Jacobo Torán

Online Publications

We offer several possibilities to publish the results of your event. Please contact publishing(at)dagstuhl.de if you are interested.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf in the library.