[My Computational Complexity Web Log] Rump Session Redux
This week I am in Amherst at the University of Massachusetts for the 19th IEEE Conference on Computational Complexity. Lots of fun papers and complexity theorists. This is complexity heaven.
Like last year, we had a number of interesting new results described at the rump session. Let me describe a couple of them to you.
Scott Aaronson follows up on his guest post about the complexity of agreement. Aumann has a famous theorem that two players who communicate cannot agree to disagree on the probability of some state of the world; after some discussion they will converge to a common probability. Aaronson looked at the complexity of this process and found that convergence comes relatively fast. He defined a notion of (ε,δ)-agreement where the probabilities are within ε of correct with a confidence of 1-δ and shows that such an agreement happens after polynomial in 1/ε and 1/δ rounds.
Neeraj Kayal looked at the complexity of the problem #RA, the number of automorphisms of a ring given by generators. He showed that factoring and graph isomorphism reduce to #RA and #RA sits in AM∩co-AM. As an open question he wondered about the complexity of determining whether a ring has nontrivial automorphisms where one is given tables for addition and multiplication. It remains open even for commutative rings.
Posted by Lance to My Computational Complexity Web Log at 6/22/2004 02:56:22 PM