I am at EVT/WOTE (Electronic Voting Technology Workshop/Workshop on Trustworthy Elections) today and tomorrow, and will try to blog about it a bit. The keynote today was given by Donetta Davidson, who runs the Election Assisstance Commission. She gave an overview of the EAC’s activities and priorities. The Q&A has focused a bit on how voting research is underfunded and that CS researchers want the EAC to lobby for more research funding. I guess some things don’t change much.
Monthly Archives: August 2010
A proof that P is not equal to NP?
Today we had the last day of the information theory summer school and Rudiger Urbanke gave a lecture on LDPC codes, random graphs, polar codes and other ways to approach Shannon Capacity.
After it was over, I received a few emails about a potential proof that P is not equal to NP from Vinay Deolalikar.
A quick look at the proof seems (to my ignorant eyes) like a serious, well-written attempt, and some people who know more seem to agree.
Surprisingly, Replica symmetry breaking, random graphs (and how they are locally tree-like) and inference on graphical models (things we discussed in the school) seem to be central in the arguments.
Let’s hope the proof is correct!