Dagstuhl Seminar 09421
Algebraic Methods in Computational Complexity
( Oct 11 – Oct 16, 2009 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/09421
Organizers
- Manindra Agrawal (Indian Institute of Technology - Kanpur, IN)
- Lance Fortnow (Northwestern University - Evanston, US)
- Thomas Thierauf (Hochschule Aalen, DE)
- Christopher Umans (CalTech - Pasadena, US)
Contact
- Annette Beyer (for administrative matters)
Schedule
The seminar brought together more than 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, most of them about 40 minutes leaving ample room for discussions. We also had a much appreciated open problem session. In the following we describe the major topics in more detail.
The talks ranged over a broad assortment of subjects with the underlying theme of using algebraic techniques. It was very fruitful 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!
- Scott Aaronson (MIT - Cambridge, US) [dblp]
- Farid Ablayev (Kazan State University, RU) [dblp]
- Vikraman Arvind (The Institute of Mathematical Sciences, IN) [dblp]
- Eli Ben-Sasson (Technion - Haifa, IL) [dblp]
- Somenath Biswas (Indian Institute of Technology - Kanpur, IN)
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Jop Briet (University of Amsterdam, NL)
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Arkadev Chattopadhyay (University of Toronto, CA) [dblp]
- Zeev Dvir (Institute of Advanced Study - Princeton, US) [dblp]
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Lance Fortnow (Northwestern University - Evanston, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- David Garcia-Soriano (CWI - Amsterdam, NL)
- William Gasarch (University of Maryland - College Park, US) [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)
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Marek Karpinski (Universität Bonn, DE) [dblp]
- Swastik Kopparty (MIT - Cambridge, US) [dblp]
- Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
- Troy Lee (Rutgers University - Piscataway, US) [dblp]
- Bruno Loff (CWI - Amsterdam, NL) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
- 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]
- Dana Moshkovitz (Institute of Advanced Study - Princeton, US) [dblp]
- Ilan Newman (University of Haifa, IL) [dblp]
- Alexander Razborov (University of Chicago, US) [dblp]
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- John D. Rogers (DePaul Uniersity - Chicago, US)
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Atri Rudra (SUNY - Buffalo, US) [dblp]
- Alex Samorodnitsky (The Hebrew University of Jerusalem, IL)
- Rahul Santhanam (University of Edinburgh, GB) [dblp]
- Nitin Saxena (Universität Bonn, DE) [dblp]
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Amir Shpilka (Technion - Haifa, IL) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Leen Torenvliet (University of Amsterdam, NL)
- Christopher Umans (CalTech - Pasadena, US) [dblp]
- Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
- Variyam N. Vinodchandran (University of Nebraska - Lincoln, US)
- Joachim von zur Gathen (Universität Bonn, DE) [dblp]
- Fabian Wagner (Universität Ulm, DE)
- Ryan Williams (IBM Almaden Center, US) [dblp]
- Sergey Yekhanin (Microsoft Corp. - Mountain View, 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 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
- verification
- logic
Keywords
- computational complexity
- algebra
- (de-) randomization
