TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 12421

Algebraic and Combinatorial Methods in Computational Complexity

( Oct 14 – Oct 19, 2012 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/12421
Organizers
Contact
Publications
Impacts
Summary
Show Summary

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 poly-logarithmic 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.

The seminar brought together more than 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic and combinatorial methods showed the great importance of such techniques for theoretical computer science. We had 30 talks, most of them lasting about 40 minutes, leaving ample room for discussions.

As is evident from the list above, the talks ranged over a broad assortment of subjects with the underlying theme of using algebraic and combinatorial techniques. It was a very fruitful meeting and has hopefully initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of techniques (rather than end results) as a unifying theme of the workshop. We look forward to our next meeting!

Participants
Show Participants
  • Farid Ablayev (Kazan State University, RU) [dblp]
  • Manindra Agrawal (Indian Institute of Technology - Kanpur, IN) [dblp]
  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Vikraman Arvind (The Institute of Mathematical Sciences, IN) [dblp]
  • Markus Bläser (Universität des Saarlandes, DE) [dblp]
  • Andrej Bogdanov (The Chinese University of Hong Kong, HK) [dblp]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • Sourav Chakraborty (Chennai Mathematical Institute, IN) [dblp]
  • Arkadev Chattopadhyay (TIFR Mumbai, IN) [dblp]
  • Samir Datta (Chennai Mathematical Institute, IN) [dblp]
  • Volker Diekert (Universität Stuttgart, DE) [dblp]
  • Klim Efremenko (Tel Aviv University, IL) [dblp]
  • Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
  • Lance Fortnow (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Anna Gál (University of Texas - Austin, US) [dblp]
  • William Gasarch (University of Maryland - College Park, US) [dblp]
  • Parikshit Gopalan (Microsoft Corp. - Mountain View, US)
  • Frederic Green (Clark University - Worcester, US) [dblp]
  • Joshua A. Grochow (University of Toronto, CA) [dblp]
  • Steve Homer (Boston University, US)
  • Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
  • Neeraj Kayal (Microsoft Research India - Bangalore, IN) [dblp]
  • Pascal Koiran (ENS - Lyon, FR) [dblp]
  • Swastik Kopparty (Rutgers University - Piscataway, US) [dblp]
  • Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Matthias Krause (Universität Mannheim, DE) [dblp]
  • Klaus-Jörn Lange (Universität Tübingen, DE) [dblp]
  • Sophie Laplante (University of Paris VII, FR) [dblp]
  • Bruno Loff (CWI - Amsterdam, NL) [dblp]
  • Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
  • Pierre McKenzie (University of Montréal, CA) [dblp]
  • Or Meir (Institute of Advanced Study - Princeton, US) [dblp]
  • Jochen Messner (Hochschule Aalen, DE) [dblp]
  • David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
  • Natacha Portier (ENS - Lyon, FR) [dblp]
  • Atri Rudra (SUNY - Buffalo, US) [dblp]
  • Chandan Saha (Indian Institute of Science - Bangalore, IN) [dblp]
  • Rahul Santhanam (University of Edinburgh, GB) [dblp]
  • Shubhangi Saraf (Rutgers University - Piscataway, US) [dblp]
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Rocco Servedio (Columbia University - New York, US) [dblp]
  • Ronen Shaltiel (University of Haifa, IL) [dblp]
  • Simon Straub (Universität Ulm, DE)
  • Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
  • Thomas Thierauf (Hochschule Aalen, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Christopher Umans (CalTech - Pasadena, US) [dblp]
  • Virginia Vassilevska Williams (Stanford University, US) [dblp]
  • Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
  • Ryan Williams (Stanford University, US) [dblp]
  • Amir Yehudayoff (Technion - Haifa, IL) [dblp]
  • David Zuckerman (University of Texas - Austin, US) [dblp]
Related Seminars
  • Dagstuhl Seminar 02421: Algebraic Methods in Quantum and Classical Models of Computation (2002-10-13 - 2002-10-18) (Details)
  • Dagstuhl Seminar 04421: Algebraic Methods in Computational Complexity (2004-10-10 - 2004-10-15) (Details)
  • Dagstuhl Seminar 07411: Algebraic Methods in Computational Complexity (2007-10-07 - 2007-10-12) (Details)
  • Dagstuhl Seminar 09421: Algebraic Methods in Computational Complexity (2009-10-11 - 2009-10-16) (Details)
  • Dagstuhl Seminar 14391: Algebra in Computational Complexity (2014-09-21 - 2014-09-26) (Details)
  • Dagstuhl Seminar 16411: Algebraic Methods in Computational Complexity (2016-10-09 - 2016-10-14) (Details)
  • Dagstuhl Seminar 18391: Algebraic Methods in Computational Complexity (2018-09-23 - 2018-09-28) (Details)
  • Dagstuhl Seminar 22371: Algebraic and Analytic Methods in Computational Complexity (2022-09-11 - 2022-09-16) (Details)
  • Dagstuhl Seminar 24381: Algebraic and Analytic Methods in Computational Complexity (2024-09-15 - 2024-09-20) (Details)
Classification
  • data structures
  • algorithm
  • complexity
  • security
  • cryptology
Keywords
  • computational complexity
  • algebra
  • combinatoric
  • (de-)randomization
Seminar 12421
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy