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.4.9.85
URN: urn:nbn:de:0030-drops-48851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4885/
Agrawal, Manindra ;
Kabanets, Valentine ;
Thierauf, Thomas ;
Umans, Christopher
Weitere Beteiligte (Hrsg. etc.): Manindra Agrawal and Valentine Kabanets and Thomas Thierauf and Christopher Umans
Algebra in Computational Complexity (Dagstuhl Seminar 14391)
Abstract
At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection 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. Representation theory has emerged as an important tool in three separate lines of work: the "Geometric Complexity Theory" approach to P vs. NP and circuit lower bounds, the effort to resolve the complexity of matrix multiplication, and a framework for constructing locally testable codes. Coding theory has seen several algebraic innovations in recent years, including multiplicity codes, and new lower bounds.
This seminar brought together researchers who are using a diverse array of algebraic methods in a variety of settings. It plays an important role in educating a diverse community about the latest new techniques, spurring further progress.
BibTeX - Entry
@Article{agrawal_et_al:DR:2015:4885,
author = {Manindra Agrawal and Valentine Kabanets and Thomas Thierauf and Christopher Umans},
title = {{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}},
pages = {85--105},
journal = {Dagstuhl Reports},
ISSN = {2192-5283},
year = {2015},
volume = {4},
number = {9},
editor = {Manindra Agrawal and Valentine Kabanets and Thomas Thierauf and Christopher Umans},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4885},
URN = {urn:nbn:de:0030-drops-48851},
doi = {10.4230/DagRep.4.9.85},
annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits}
}
|
Keywords: |
|
Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits |
|
Collection: |
|
Dagstuhl Reports, Volume 4, Issue 9 |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
27.01.2015 |
