October 11 – 16 , 2009, Dagstuhl Seminar 09421

Algebraic Methods in Computational Complexity


Manindra Agrawal (Indian Institute of Technology – Kanpur, IN)
Lance Fortnow (Northwestern University – Evanston, US)
Thomas Thierauf (Hochschule Aalen, DE)
Christopher Umans (CalTech – Pasadena, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl Seminar Schedule [pdf]


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!

Dagstuhl Seminar Series


  • Data Structures
  • Algorithms
  • Complexity
  • Security
  • Cryptography
  • Verification
  • Logic


  • Computational complexity
  • Algebra
  • (de-) randomization


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.