The FOCS program is now online here.Congratulations to Yin Tat Lee and Aaron Sidford for winning the best paper and the best student paper awards for their paper "Solving Linear Programs in O˜(√rank) Iterations and Faster Algorithms for Maximum Flow". They made an important advance in the theory of interior point methods by showing that you can actually … Continue reading FOCS 2014 program is online

[Boaz's note: videos of all ICM 2014 talks, including Mark's talk discussed below, as well as the talks of  Candes and Bhargava I mentioned before are available online here. In particular, if you still don't know how one constructs a fully homomorphic encryption scheme then you should (a) be ashamed of yourself and (b) watch Craig Gentry's … Continue reading ICM 2014: Mark Braverman on interactive information theory

This week I'm at the International Congress of Mathematicians  (ICM) 2014 in Seoul, and thought I would post a quick update from a TCS perspective. See Tim Gowers's blog for a much more comprehensive account. There are several other TCS folks here, and I hope some would also post their impressions and recommendations as well. For TCS the … Continue reading Updates from ICM 2014

Guest post by Craig Gentry The 2014 International Congress of Mathematicians (ICM 2014) is coming up in a few days, and (like Boaz said) we have a great collection of speakers in the "Mathematical Aspects of Computer Science" section. As it is the weekend, and I am sure that you are looking for excuses to … Continue reading ICM survey: Computing on the edge of chaos

The accepted papers list for FOCS 2014 is now posted online. I am always amazed by the depth and breadth of works in the TCS community, and this FOCS is no exception. Whether you are a physicist interested in the possibility of general "area law" governing entanglement between different parts of systems, a geometer interested in Gromov's topological notion of … Continue reading FOCS 2014 Accepted papers list is online

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 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

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

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