I promised to blog regarding the FOCS work and I did it to some extent. But not as much as I thought I would. Turns out that chairing was not conducive to blogging (or to much of the other things I planned on doing). Feel free to ask me questions here, and I’ll do my … Continue reading Some Reflections on the FOCS PC Work
Category: Uncategorized
GM Turing Award, words by Avi Wigderson
In celebration of the the Goldwasser-Micali Turing Award, Avi Wigderson wrote the lyrics for two songs based on familiar tunes. They were performed by a Malaysian singer found on Mechanical Turk (Avi promises a more professional version some day). The songs and lyrics are included for your enjoyment: Crypto boy CryptoBoy lyrics Killer queen KillerQueen lyrics
Discrepancy, Graphs, and the Kadison-Singer Problem
Discrepancy theory seeks to understand how well a continuous object can be approximated by a discrete one, with respect to some measure of uniformity. For instance, a celebrated result due to Joel Spencer says that given any set family $latex {S_1,\ldots,S_n\subset [n]}&fg=000000$, it is possible to color the elements of $latex {[n]}&fg=000000$ Red and Blue … Continue reading Discrepancy, Graphs, and the Kadison-Singer Problem
FOCS 2013 – Accepted Papers
While there is a long tail of tasks ahead of us, the FOCS 2013 PC have completed its main task – selecting the program. The list of accepted papers is appended to this post, and I think it is a great collection of papers! We have unfortunately rejected many good papers, either because the presentation … Continue reading FOCS 2013 – Accepted Papers
Prices, Competition, and Captivity
Imagine that two technology companies A and B sell similar products (e.g. phones) and they compete for customers. Some customers are loyal to one company or the other, perhaps because they already have products from company A that are incompatible with offerings from company B or visa-versa. Other customers are willing to buy either product … Continue reading Prices, Competition, and Captivity
Away with Page Limits on Submissions (II)
As discussed here, the FOCS 2013 PC did not impose page limit on submissions. As this was an experiment, it is important to try and assess its success. Clearly, no page limit in itself makes it easier on the authors, but we tried to make the CFP more demanding on authors in terms of presentation. … Continue reading Away with Page Limits on Submissions (II)
Craving for Stories
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
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
Windows On Theory 