http://www.dagstuhl.de/09421

October 11 – 16, 2009, Dagstuhl Seminar 09421

Algebraic Methods in Computational Complexity

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)


For support, please contact

Dagstuhl Service Team

Documents

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

Summary

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

Classification

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

Keywords

  • Computational complexity
  • Algebra
  • (de-) randomization

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

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).

Publications

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

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.