Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Rump Session Redux

Expand Messages
  • Lance
    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
    Message 1 of 1 , Jun 22, 2004
    • 0 Attachment
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.