TheoryFest begins

I arrived to Montreal tonight and already marked the talks I want to attend on the STOC mobile app. I am looking forward to a great program.

I am already seeing several times that I would like to attend two or three of the talks that occur in parallel. One day where this would definitely be the case is during the workshops.

All of them seem very interesting. Eli mentioned the workshop on PCP’s. It’s amazing to see how the probabilistically checkable proofs, that at the time I was a student seemed like the quintessential hard and abstract area of theory, is now the foundations for startup companies.

The workshop on “user friendly” methods from continuous optimization could also be very useful. One of the drawbacks to a method being so useful is that because many communities use it, the same concepts can be described in very different ways and terminologies.  Recently some significant advances were made by bridging together ideas from optimization and TCS, and this workshop is organized by some of the experts who did that, and can help the rest of us understand these different viewpoints.

The workshop on mechanism design has a packed schedule of many of the experts in this area including sessions about the tradeoffs of simplicity (which is often crucial for mechanism) and connections to learning. Speaking of learning , the workshop on machine learning  has a full day of talks on what is now one of the most active areas of interaction with theory. In fact, learning research is so active that it has direct interactions with several of the areas (such as continuous optimization, mechanism design, and sum of squares) that are in the concurrent workshops… but we TCS people know that bounded resources often necessitate tradeoffs.

I am involved in organizing (with  Pablo Parrilo and Tselil Schramm) one of the workshops – on the sum of squares algorithm . This workshop will consist of tutorial style talks, that assume only general TCS background, but will talk also about very recent works.

Pablo (who is one of the inventors of the SOS algorithm) will talk about some of its applications outside TCS and then about how the symmetry reduction technique, which is important in practical applications, turns out to be also crucial for proving combinatorial inequalities on graphs using flag algebras.

Tselil will talk about spectral algorithms inspired by SOS, and how these can be used to give new algorithms, and sometimes even quite efficient ones, that avoid using general SDP solvers.

Sam Hopkins will talk on obtaining SOS lower and upper bounds using a computational Bayesian perspective in the context of planted problems such as planted clique, community detection, etc.., and how low degree statistics play a crucial role.

Finally, I will talk about whether SOS could be an “optimal algorithm” and what’s the relation to Khot’s Unique Games Conjecture.  If you want to know what this means, or are one of the people who cringe at the notion of an “optimal algorithm” and want to upbraid me in person, this  talk will be for you.