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