Dagstuhl-Seminar 12421
Algebraic and Combinatorial Methods in Computational Complexity
( 14. Oct – 19. Oct, 2012 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/12421
Organisatoren
- Manindra Agrawal (Indian Institute of Technology - Kanpur, IN)
- Thomas Thierauf (Hochschule Aalen, DE)
- Christopher Umans (CalTech - Pasadena, US)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Annette Beyer (für administrative Fragen)
Impacts
- Space-Efficient Approximations for Subset Sum - Gal, Anna; Jang, Jing-Tang; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek - Potsdam : Hasso-Plattner-Institut, 2014. - 31 S. - (Electronic Colloquium on Computational Complexity, Report ; 14-180).
- Topology Matters in Communication : article in 2014 IEEE Annual Symposium on Foundations of Computer Science : pp. 631-640 - Chattopadhyay, Arkadev; Radhakrishnan, Jaikumar; Rudra, Atri - Los Alamitos : IEEE, 2014. - pp. 631-640 - (2014 IEEE Annual Symposium on Foundations of Computer Science FOCS).
- Unifying and generalizing known lower bounds via geometric complexity theory - Grochow, Joshua A. - Cornell University : arXiv.org, 2013. - 31 pp..
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!
- 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]
Verwandte Seminare
- 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)
Klassifikation
- data structures
- algorithm
- complexity
- security
- cryptology
Schlagworte
- computational complexity
- algebra
- combinatoric
- (de-)randomization
