License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.8.9.133
URN: urn:nbn:de:0030-drops-103438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10343/
Bläser, Markus ;
Kabanets, Valentine ;
Torán, Jacobo ;
Umans, Christopher
Weitere Beteiligte (Hrsg. etc.): Markus Bläser and Valentine Kabanets and Jacobo Torán and Christopher Umans
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391)
Abstract
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.
In some of the most exciting recent progress in Computational Complexity the algebraic theme still plays a central role. 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). Also the areas of derandomization and coding theory have experimented important advances.
The seminar aimed 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 the goal of the seminar was to play an important role in educating a diverse community about the latest new
techniques.
BibTeX - Entry
@Article{blser_et_al:DR:2019:10343,
author = {Markus Bl{\"a}ser and Valentine Kabanets and Jacobo Tor{\'a}n and Christopher Umans},
title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391)}},
pages = {133--153},
journal = {Dagstuhl Reports},
ISSN = {2192-5283},
year = {2019},
volume = {8},
number = {9},
editor = {Markus Bl{\"a}ser and Valentine Kabanets and Jacobo Tor{\'a}n and Christopher Umans},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10343},
URN = {urn:nbn:de:0030-drops-103438},
doi = {10.4230/DagRep.8.9.133},
annote = {Keywords: computational complexity, algebra, (de-) randomization, circuits, coding, lower bounds}
}
|
Keywords: |
|
computational complexity, algebra, (de-) randomization, circuits, coding, lower bounds |
|
Collection: |
|
Dagstuhl Reports, Volume 8, Issue 9 |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
25.03.2019 |
