10. – 15. Oktober 2004, Dagstuhl-Seminar 04421

Algebraic Methods in Computational Complexity


Harry Buhrman (CWI – Amsterdam, NL)
Lance Fortnow (University of Chicago, US)
Thomas Thierauf (FH 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 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 saw a series of presentations by Andris Ambainis, Robert Spalek and Mario Szegedy. Ambainis described his improved method for showing lower bounds for quantum algorithms that provably beats the degree method. Spalek talked about his work with Szegedy showing that Ambainis techniques as well as different tools developed by Zhang, Laplante and Magniez, and Barnum, Saks and Szegedy all gave the same bounds. Szegedy, in his presentation, called this measure the div complexity and showed that the size of a Boolean formula computing a function f is at least the square of the div complexity of f . Further talks on quantum complexity considered lower bounds for formula size (Scott Aaronson), finite groups (Steve Fenner), and adversary bounds (Robert Spalek).

Discussions between Laplante, Lee and Szegedy at the workshop led to the recent announcement of even a stronger lower bound for Boolean formula complexity using a stronger version of div complexity called maxPI.

Manindra Agrawal presented recent work of his students Neeraj Kayal and Nitin Saxena (the trio that showed a polynomial-time algorithm for primality testing) on rings given by a matrix describing the actions on the base elements. They show a randomized reduction from graph isomorphism to ring isomorphism and from factoring to # RI , counting the number of ring isomorphisms. They also show a polynomial-time algorithm for determining if there are any non-trivial automorphisms of a ring and that # RI is computable with an oracle for AMcoAM . Agrawal conjectured that # RI is computable in polynomial time, a conjecture that would imply factoring and graph isomorphism have efficient algorithms.

In addition to Agrawal's presentation on ring isomorphism, we had a wide-range of talks on classical complexity. Lance Fortnow, building on work of Shaltiel and Umans, characterized the interesting question whether EXP is contained in NP with logarithmically bounded advice. Judy Goldsmith showed that the dominance problem for user preferences is PSPACE complete. Various hypothesis in complexity theory were compared by John Hitchcock. Jörg Rothe located the Exact-Four-Colorability problem in the boolean hierarchy. Several probabilistic time classes were separated by Rahul Santhanam. Leen Torenvliet considered autoreducible sets and Falk Unger presented some new results on sparse self-reducible sets. Talks on circuit complexity were given by Anna Gal, Ryan O'Donnell and Denis Therien.

Troy Lee considered the symmetry of information in Kolmogorov complexity. Klaus Ambos-Spies presented algorithmic and resource-bounded genericity concepts. Tolerant property tester were investigated by Eldar Fischer, and automatic structures by Frank Stephan. Markus Maucher presented a very interesting relationship between the entropy of random source and the running time of (randomized) quicksort, where the random source is used for the choice of the pivot element. Rüdiger Reischuk considered string compression based on context-free grammars: the problem to determine the minimal size of a grammar that produces precisely one given string x was shown to be NP-hard for alphabets of larger size.

Dagstuhl-Seminar Series


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.