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
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 09421

Algebraic Methods in Computational Complexity

( Oct 11 – Oct 16, 2009 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:





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)

  • data structures
  • algorithms
  • complexity
  • security
  • cryptography
  • verification
  • logic

  • computational complexity
  • algebra
  • (de-) randomization