A Caltech Library Service

Algebraic and Combinatorial Methods in Computational Complexity

Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher (2012) Algebraic and Combinatorial Methods in Computational Complexity. Dagstuhl Reports, 2 (10). pp. 60-78. ISSN 2192-5283. doi:10.4230/DagRep.2.10.60.

[img] PDF - Published Version
Creative Commons Attribution Non-commercial No Derivatives.


Use this Persistent URL to link to this item:


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 (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 PCP characterization of NP and the Agrawal-Kayal-Saxena polynomial-time primality test are two prominent examples. Recently, there have been some works going in the opposite direction, giving alternative combinatorial proofs for results that were originally proved algebraically. These alternative proofs can yield important improvements because they are closer to the underlying problems and avoid the losses in passing to the algebraic setting. A prominent example is Dinur's proof of the PCP Theorem via gap amplification which yielded short PCPs with only a polylogarithmic length blowup (which had been the focus of significant research effort up to that point). We see here (and in a number of recent works) an exciting interplay between algebraic and combinatorial techniques. This seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and combinatorial methods in a variety of settings.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2012 Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Creative Commons BY-NC-ND 3.0 Unported license. Dagstuhl Seminar 12421.
Subject Keywords:Computational Complexity, lower bounds, approximazation, pseudorandomness, derandomization, circuits
Issue or Number:10
Classification Code:1998 ACM Subject Classification: F.1.3 Complexity Measures and Classes, F.2 Ananlysis of Algorithms and Problem Complexity
Record Number:CaltechAUTHORS:20191126-143839781
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100075
Deposited By: Tony Diaz
Deposited On:26 Nov 2019 22:46
Last Modified:16 Nov 2021 17:51

Repository Staff Only: item control page