## FOCS 2014 Accepted papers list is online

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 expanders, an optimization expert interested in the latest and greatest in interior point methods, a game theorist interested in Karlin’s longstanding conjecture on convergence of fictitious play, a complexity theorist interested in the latest efforts to separate the determinant from the permanent, or simply a dog owner or triangle lover, you will find something of interest in the conference. And of course FOCS is not just a collection of unrelated papers. A quantum computing expert would want to check the paper on topological expanders, as similar concepts have arose in the context of topological approaches to quantum error correction. An optimization expert might want to understand the convergence of “fictitious play” which is a very natural algorithm for solving linear programs, and of course since STOC 2014 we all know that circuit lower bounds are tightly connected to improving the exponents of algorithms for combinatorial problems. This is just a taste and I could have chosen many other such examples, all strengthening Avi Wigderson’s point why we should all go to talks in areas other than our own.

I was also amazed by the effort reviewers and program committee members have put in the selection process. Conference reviewing sometimes get a bad reputation as being superficial. I did not find this to be the case at all. People have invested an amazing amount of work reading the papers, checking proofs, chasing down references, verifying technical points with the authors and other experts, and generally doing the best job they can to have an informed selection process and assemble the best program we can for the TCS community. I am sure we made mistakes, and the final program, as a product of a committee, is not fully consistent with any particular PC member’s taste, including my own. In particular, there were many submissions that some of us personally found novel and interesting, but were not included in the final program. But I do feel good about the process and believe that while some of our decisions may have been wrong, they were not wrong because we were superficial or lazy or cut corners due to the time pressure. Many times during this process I asked the PC members to go above and beyond what is typically expected, and they have more than risen to this challenge, often making heroic efforts to understand very complex (and sometimes not so greatly written) papers, and trying to get to the bottom of any misunderstanding. I am deeply grateful to them all.

Finally, some statistics. We accepted 70 papers, which is about 26% of the 268-273 submissions (depending on whether you count withdrawn ones). Aside from 9 submissions that were judged to be out of scope and received minimal reviewing, on average each submission had 3.3 reviews and 11.7 comments (including both comments by the PC and short comments/opinions by outside experts that were solicited in addition to the reviews.) Of course these numbers varied greatly based on how much attention and investigation we felt each submission needed and there was also extensive discussion on some of the papers during our two long days of the physical PC meeting. Finally, a very personal statistic for me is that there are about 2800 emails in my “FOCS14″ folder. As many past chairs told me, the best thing about this job is that you only do it once…

## Independent conferences: the second-worst solution

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. But, I am not happy about this outcome. I think that having our conferences under an umbrella such as ACM or IEEE that unities much of Computer Science is a positive thing, regardless of practical issues such as bank accounts, insurance, hotel deals etc.. (that thankfully I understand very little about) or even issues such as “prestige” and library subscriptions. I am afraid that an administrative isolation of a sub-area might end up contributing to an intellectual isolation as well. For example, while the idea might sound appealing, I think it is good that we don’t typically have “department of theoretical computer science” (let alone a department of computational complexity or computational geometry). It is important for us to interact with other computer scientists, if only so that we can occasionally torture them with an equation-filled colloquium talk :)

As I said in the past, I wish that our professional societies would behave more like their mission statements and less like for-profit publishers, and so conferences would not feel compelled to leave them. Given the hundreds of votes in the CCC and SoCG elections, I can’t help but think that if steering committees and chairs of various SIGs across all Computer Science collaborated together, they could marshal thousands of votes in the ACM elections that would truly change how it operates.

** Update:** Please see Paul Beame’s comment below for some of the significant differences between ACM and IEEE.

## ICM Survey: Codes with local decoding procedures

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 used in data storage applications to provide a more space efficient alternative to RAID. Below is the abstract of the survey:

Error correcting codes allow senders to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message can still be recovered even if a fraction of the codeword bits are corrupted. In certain settings however the receiver might not be interested in recovering all the message, but rather seek to quickly recover just a few coordinates of it. Codes that allow one to recover individual message coordinates extremely fast (locally), from accessing just a small number of carefully chosen coordinates of a corrupted codeword are said to admit a local decoding procedure. Such codes have recently played an important role in several areas of theoretical computer science and have also been used in practice to provide reliability in large distributed storage systems. We survey what is known about these codes.

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*. While typically we think of an algorithm as tailor-made for a particular problem, there are some generic approaches to design an “algorithmic scheme” or a *meta algorithm*, that can be applied to a large class of problems. The UGC predicts that a particular such meta-algorithm, which we call in the survey simply the “UGC Meta-Algorithm”, would give in fact *optimal approximation guarantees *among all efficient algorithms for a large class of problems. This is very exciting from the point of view of complexity theory, not simply because it gives many hardness-of-approximation results in one shot, but because in some sense it gives a complete understanding of what makes problems of certain domains easy or hard.

The SOS method is another meta algorithm that can be applied to the same cases. It is parameterized by a number called its *degree. *Using a higher degree can give potentially better approximation guarantees, at the expense of longer running time: running the method with degree on input of length takes time. The UGC Meta-Algorithm in fact corresponds to the base case (which is degree ) of the SOS method, and so the UGC predicts that in a great many cases, using constant (even even mildly super-constant) degree larger than will not help get better approximation guarantees. We discuss in the survey a few recent results that, although falling short of refuting the UGC, cast some doubts on this prediction by showing that larger degree can sometimes help in somewhat similar contexts. I will give a talk on the same topic in the mathematical aspects of computer science section of the 2014 International Congress of Mathematicians to be held in Seoul, South Korea, August 13-21, 2014. As you can see, there will be some great speakers in this session (and ICM in general), and I hope we will see blog posts on some of those surveys as well.