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.

Update 6/23: Kayal tells me I didn't accurately capture his rump session talk and sent me the following summary.

We have an algorithm that determines whether a ring has a nontrivial isomorphism even when the ring is given in the form of generators for its additive group and pairwise product of the generators expressed as a linear combination of the generators. (We get this by getting a characterization of all finite rigid rings and it turns out that we can test whether a ring follows this characterization or not without solving integer factoring.) Unfortunately however we do not know of a reduction from Graph automorphism to ring automorphism although we have found a cute reduction from Graph Isomorphism to Ring Isomorphism!

The open problem that I would love to solve is to decide whether two rings are isomorphic or not when they are given in the form of tables (one table each for addition and multiplication.) I do not know how to do this even for commutative rings.