07. – 12. Oktober 2007, Dagstuhl-Seminar 07411

Algebraic Methods in Computational Complexity


Manindra Agrawal (Indian Institute of Technology – Kanpur, IN)
Harry Buhrman (CWI – Amsterdam, NL)
Lance Fortnow (Northwestern University – Evanston, US)
Thomas Thierauf (Hochschule Aalen, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
Dagstuhl's Impact: Dokumente verfügbar


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!

Dagstuhl-Seminar Series


  • Data Structures / Algorithms / Complexity
  • Security / Cryptography


  • Computational complexity
  • Algebra
  • Quantum computing
  • (de-) randomization


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.