A Caltech Library Service

Algebraic and Combinatorial Methods in Computational Complexity

Kabanets, Valentine and Thierauf, Thomas and Torán, Jacobo and Umans, Christopher (2016) Algebraic and Combinatorial Methods in Computational Complexity. Dagstuhl Reports, 6 (10). pp. 13-32. ISSN 2192-5283. doi:10.4230/DagRep.6.10.13.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. 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 are some of the most prominent examples. The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called chasm at depth 4 suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model (and these are tied to central questions regarding the power of randomness in computation). Another surprising connection is that the algebraic techniques invented to show lower bounds now prove useful to develop efficient algorithms. For example, Williams showed how to use the polynomial method to obtain faster all-pair-shortest-path algorithms. This emphases once again the central role of algebra in computer science. The seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar can play an important role in educating a diverse community about the latest new techniques, spurring further progress.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2016 Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Creative Commons BY 3.0 Unported license. Report from Dagstuhl Seminar 16411.
Subject Keywords:Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits
Issue or Number:10
Classification Code:1998 ACM Subject Classification: F.1.3 Complexity Measures and Classes, F.2 Analysis of Algorithms and Problem Complexity
Record Number:CaltechAUTHORS:20191118-153821359
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99912
Deposited By: Tony Diaz
Deposited On:18 Nov 2019 23:59
Last Modified:16 Nov 2021 17:50

Repository Staff Only: item control page