Dagstuhl Seminar 07411
Algebraic Methods in Computational Complexity
( Oct 07 – Oct 12, 2007 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/07411
Organizers
- Manindra Agrawal (Indian Institute of Technology - Kanpur, IN)
- Harry Buhrman (CWI - Amsterdam, NL)
- Lance Fortnow (Northwestern University - Evanston, US)
- Thomas Thierauf (Hochschule Aalen, DE)
Contact
- Simone Schilke (for administrative matters)
The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks of length between 15 and 45 minutes. This left enough room for discussions. We had an open problem session that was very much appreciated. In the following we describe the talks in more detail.
The construction of good extractors and expanders plays a crucial role in derandomization. Chris Umans explained how to construct highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree, essentially optimal. The construction is based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS `05). Anup Rao considered the model that the source, a family of distributions, gives a random point from some unknown low dimensional affine subspace with a low-weight basis. This model generalizes the well studied model of bit-fixing sources. He showed how to construct new extractors for this model that have exponentially small error, a parameter that is important for applications in cryptography.
Derandomization is strongly related to proving lower bounds. In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP: if one cannot derandomize BPP, then E needs exponential size circuits. Ronen Shaltiel considered the Artur-Merlin class AM instead of BPP. He showed uniform hardness vs.\ randomness tradeoffs for AM that are near-optimal for the full range of possible hardness assumptions.
As is evident from the list above, the talks ranged a wide area of subjects with the underlying of using algebraic techniques. It was very fruitful and has hopefully initiated new directions in research. We look forward to our next meeting!
- Scott Aaronson (MIT - Cambridge, US) [dblp]
- Farid Ablayev (Kazan State University, RU) [dblp]
- Manindra Agrawal (Indian Institute of Technology - Kanpur, IN) [dblp]
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Andris Ambainis (University of Latvia - Riga, LV) [dblp]
- Vikraman Arvind (Chennai Mathematical Institute, IN) [dblp]
- Somenath Biswas (Indian Institute of Technology - Kanpur, IN)
- Jop Briet (CWI - Amsterdam, NL)
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Richard Chang (University of Maryland, Baltimore Country, US)
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Eldar Fischer (Technion - Haifa, IL)
- Lance Fortnow (Northwestern University - Evanston, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Christian Glasser (Universität Würzburg, DE) [dblp]
- Frederic Green (Clark University - Worcester, US) [dblp]
- John Hitchcock (University of Wyoming - Laramie, US)
- Thanh Minh Hoang (Universität Ulm, DE)
- Steve Homer (Boston University, US)
- Peter Hoyer (University of Calgary, CA) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Julia Kempe (Tel Aviv University, IL)
- Hartmut Klauck (Universität Frankfurt, DE) [dblp]
- Adam Klivans (University of Texas - Austin, US)
- Sophie Laplante (Université Paris Sud, FR) [dblp]
- Troy Lee (Rutgers University - Piscataway, US) [dblp]
- Jack H. Lutz (Iowa State University, US)
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
- Ryan O'Donnell (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Anup Rao (University of Texas - Austin, US) [dblp]
- Oded Regev (Tel Aviv University, IL) [dblp]
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- John D. Rogers (DePaul University - Chicago, US)
- Rahul Santhanam (University of Toronto, CA) [dblp]
- Nitin Saxena (CWI - Amsterdam, NL) [dblp]
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Rocco Servedio (Columbia University - New York, US) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Ben Toner (CWI - Amsterdam, NL)
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (CalTech - Pasadena, US) [dblp]
- Falk Unger (CWI - Amsterdam, NL)
- Wim van Dam (University of California - Santa Barbara, US) [dblp]
- Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
- Variyam N. Vinodchandran (University of Nebraska - Lincoln, US)
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Ingo Wegener (TU Dortmund, DE)
- Marius Zimand (Towson University, US)
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 09421: Algebraic Methods in Computational Complexity (2009-10-11 - 2009-10-16) (Details)
- Dagstuhl Seminar 12421: Algebraic and Combinatorial Methods in Computational Complexity (2012-10-14 - 2012-10-19) (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 / algorithms / complexity
- security / cryptography
Keywords
- computational complexity
- algebra
- quantum computing
- (de-) randomization
