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
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!
Research Life-Stories: Erin Wolf Chambers
Next story on our project from Erin Wolf Chambers: ------------------------ I spent most of my first couple of years of graduate school unsuccessfully trying to figure out what "research" meant. I read papers and had plenty of meetings, but somehow had no luck really making new progress on any of the problems I looked at. … Continue reading Research Life-Stories: Erin Wolf Chambers
Windows On Theory 