My FOCS PC work slows down the flow of stories (but feel free to send me your stories without all the redundant arm twisting, you know I’ll get to you at some point anyway 😉 ). In the meanwhile, here are two pointers that are relevant. First, People of ACM has some great stories. In particular, … Continue reading Craving for Stories
Month: May 2013
On the Importance and Risks in Using Sub-Reviewers
I promised to post from time to time about the FOCS 2013 PC work (to demystify the process). So here is a quick update: We got 280 submission (well, 281 submissions but one was just a bad joke). This is up (by more than %10) from FOCS 2012 but on the other hand our PC … Continue reading On the Importance and Risks in Using Sub-Reviewers
On the importance of the alphabet
In my last post, we saw that the problem of learning juntas, hard as it is over Boolean inputs, seems even worse over other alphabets. Coding theory happens to have a inexhaustible supply of such problems. Some of these are long-standing open problems, others are of a more recent vintage. More of these problems seem to crop up … Continue reading On the importance of the alphabet
Reasons to care: In honor of Scott Aaronson
Update (5/7): This post earned me a spot on the not-so-exclusive club of people called names such as a "narrow-minded" "biased" "religious worshiper" "who doesn't want to learn something difficult and new" by Luboš Motl. Interestingly, he mostly takes issue with my discounting the possibility that the complexity of SAT is something like $latex n^{1000}$ or $latex … Continue reading Reasons to care: In honor of Scott Aaronson
The New Yorker on P vs NP
A new review is out for Lance Fortnow's new book "The Golden Ticket: P, NP and the Search for the Impossible". In another piece of news: congratulations to new members of the National Academy of Science Éva Tardos and Avi Wigderson!
Windows On Theory 