Algebraic Methods in Computational Complexity

Summary

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 AM ∩ coAM . 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.