Thursday, June 09, 2011

An Update on Impagliazzo's Worlds

Russell Impagliazzo gave a talk at Complexity about his five worlds. We didn't know whether Heuristica and Algorithmica were different, i.e., whether if NP is easy on average then its also easy in the worst case. Russell gave an oracle relative to which where NP is easy on average but P ≠ NP. There are now relativized separations of all his worlds.

Russell announced that it was his first talk ever using a computer instead of transparencies. We gave a round of applause welcoming him to 1998. His talk consisted of some PowerPoint slides with black text on a generic white background and some very cute hand-drawn cartoons that he scanned in to his talk. Someone asked for animation. Maybe next decade.

In less than an hour new Stanford professor Ryan Williams gives the Complexity talk on his great result that NEXP not in ACC0. With no surprise, Ryan won the Complexity best paper award, the second-highest honor his paper has received.

No comments:

Post a Comment

Post a Comment