The steering committee of the Conference on Computational Complexity has decided to become independent of IEEE. The Symposium of Computational Geometry is considering leaving ACM for similar reasons. I completely understand the reasons, and applaud the steering committees in both cases for having a thoughtful, deliberate, and transparent process. Indeed, I have signed the letter of support for CCC. … Continue reading Independent conferences: the second-worst solution

I have recently completed a survey “Codes with local decoding procedures” and will be giving a talk on this matter in August at the ICM. The survey covers two related families of codes with locality, namely, locally decodable codes that are broadly useful in theoretical computer science and local reconstruction codes that have recently been … Continue reading ICM Survey: Codes with local decoding procedures

I have just posted online a new survey "Sum-of-Squares proofs and the quest toward optimal algorithms" co-authored with David Steurer . The survey discusses two topics I have blogged about before - Khot's Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method - and the connections between them. Both are related to the notion of meta algorithms. … Continue reading ICM Survey: Sum-of-squares proofs and the quest toward optimal algorithms

In this post, I am going to give you a simple, self-contained, and fruitful demonstration of a recently introduced proof technique called the method of interlacing families of polynomials, which was also mentioned in an earlier post. This method, which may be seen as an incarnation of the probabilistic method, is relevant in situations when … Continue reading Restricted Invertiblity by Interlacing Polynomials

And is linked from the Call for Papers. (The url for the server is http://focs2014.cs.princeton.edu , though please do read the call for paper, and the advice linked below, before submitting.) We are continuing the FOCS 2013 experiment of less regulation and more responsibility on the paper formatting, so please do read my advice for authors before submitting. … Continue reading FOCS 2014 submission server is now open

In the previous posts we talked about various discrepancy questions and saw a proof of the six standard deviations suffice result. Besides being of interest in combinatorics, discrepancy theory has several remarkable applications in algorithms. Check this excellent book for a taste of these results. Here I will briefly discuss two (one old and one … Continue reading Discrepancy and Rounding Linear Programs

In the last post we discussed some questions about discrepancy and the 'Six Standard Deviations Suffice' theorem stated below (without the $latex {6}&fg=000000$, which is not too important, but makes for a great title): Theorem 1 For vectors $latex {a^1,\ldots,a^n \in \{1,-1\}^n}&fg=000000$, there exists $latex {\epsilon \in \{1,-1\}^n}&fg=000000$ such that for every $latex {j \in … Continue reading Discrepancy Bounds from Convex Geometry

This blog post is an introduction to the ``Sum of Squares'' (SOS) algorithm from my biased perspective. This post is rather long - I apologize. You might prefer to view/print it in pdf format. If you'd rather "see the movie", I'll be giving a TCS+ seminar about this topic on Wednesday, February 26th 1pm EST. … Continue reading Fun and Games with Sums of Squares

[Update 5/20/14: Feel free to borrow or adapt any part of this text for future conferences. In retrospect, perhaps I should have given some more concrete guidance: in a typical TCS paper, by page 5 or 6 you should be done with the introduction, which means that you have already clearly stated your main result, explained why … Continue reading Advice for FOCS authors