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.

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