License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.2.10.60
URN: urn:nbn:de:0030-drops-39034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3903/
Go back to Dagstuhl Reports

Agrawal, Manindra ; Thierauf, Thomas ; Umans, Christopher
Weitere Beteiligte (Hrsg. etc.): Manindra Agrawal and Thomas Thierauf and Christopher Umans

Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)

pdf-format:
dagrep_v002_i010_p060_s12421.pdf (1 MB)

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 (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.

BibTeX - Entry

@Article{agrawal_et_al:DR:2013:3903,
  author =	{Manindra Agrawal and Thomas Thierauf and Christopher Umans},
  title =	{{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}},
  pages =	{60--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{10},
  editor =	{Manindra Agrawal and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3903},
  URN =		{urn:nbn:de:0030-drops-39034},
  doi =		{10.4230/DagRep.2.10.60},
  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 2, Issue 10
Issue Date: 2013
Date of publication: 18.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI