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

[Computational Complexity] Conference Accepts

Expand Messages
  • Lance
    A number of summer conferences specifically had their submission deadlines soon after the STOC decision date in early February. Now these conferences have made
    Message 1 of 1 , Apr 15, 2009
    • 0 Attachment
      A number of summer conferences specifically had their submission deadlines soon after the STOC decision date in early February. Now these conferences have made their own decisions so go check out the accepted papers of Computational Complexity, ICALP, EC and COCOON.

      Speaking of STOC, early registration deadline of April 28th is fast approaching. Bill and I will both be there.

      Lots of great papers in the Complexity Conference headlined by Braverman but let me focus on the paper One-Way Functions and the Isomorphism Conjecture by Manindra Agrawal and Osamu Watanabe. That is the Agrawal of Primes in P fame. Kayal and Saxena each have Complexity papers as well.

      Many complexity theorists don't believe the Berman-Hartmanis Isomorphism Conjecture, that all NP-complete sets are essentially the same, because the conjecture fails given sufficiently hard one-way functions. Agrawal and Watanabe argue that the one-way functions that we commonly see in cryptography have an easy to invert "cylinder" which allows one to achieve an isomorphism for NP-complete sets based on using these functions as reductions. Agrawal and Watanabe show roughly that under an assumption that all such functions have such cylinders one gets nonuniform isomorphisms. 

      Given the Agrawal-Watanabe paper I started to believe that maybe the Berman-Hartmanis conjecture holds after all. On the other hand, Oded Goldreich has since given a candidate one-way function that may not have the cylinder property. Now I don't know what to believe.








      --
      Posted By Lance to Computational Complexity at 4/15/2009 06:02:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.