Celebrating TCS at STOC 2017

STOC 2017 is going to be part of an expanded “Theory Festival” which will include not just the paper presentations, but a host of other activities such as plenary talks and tutorials, workshops, and more.

One of the components I am most excited about is a sequence of invited plenary short talks where we will get a chance to hear about some exciting recent theoretical works from a variety of areas from areas as disparate as theoretical physics and network programming languages, and many others in between.

As the chair of the committee to select these talks, I was very fortunate for the work of the committee members as well as the many nominations we received from leading researchers across a great many fields.  I am also grateful to all the speakers that agreed to come despite the fact that in most cases STOC is not their “home conference”.  The end result is a collection of talks that is sure to contain interesting and new content for every theoretical computer scientist, and I encourage everyone who can make it to register to the conference and come to Montreal in June.

Here is some information about the talks (in the order of scheduling).

The short descriptions of the talks below are mine and not the authors’: more formal and informative (and maybe even correct 🙂 ) abstracts will be posted closer to the event.

 

Tuesday, June 20, 3:50pm-5:30pm

Alon Orlitsky: Competitive Distribution Estimation: Why is Good-Turing Good

Estimating a distribution from samples is one of the most basic questions in information theory and data analysis, going at least far back to Pearson’s work in the 1800’s. In Alon’s wonderful NIPS 2015 paper with Ananda Theertha Suresh (which also won the NIPS best paper award) they showed that a somewhat mysterious but simple estimator is nearly-optimal in the sense of providing good competitive guarantees even against ideal offline estimators that have more information.

 

John Preskill: Is spacetime a quantum error-correcting code?

20th century physics’ quest for a “theory of everything” had encountered a “slight hitch” in that the two most successful theories: general relativity and quantum mechanics, are inconsistent with one another.  Perhaps the most promising approach towards reconciling this mismatch is a 20 years old conjectured isomorphism between two physical theories, known as the “AdS/CFT correspondence“. A great many open questions relating to this approach remain; over the past several years, we have learned that quantum information science might shed light on these fundamental questions.  John will discuss some of the most exciting developments in this direction, and in particular will present his recent  Journal of High Energy Physics paper with Pastawski, Yoshida, and Harlow which connects quantum gravity (and black holes in particular), to issues in quantum information theory and specifically to quantum error correcting codes.

 

Tim Roughgarden: Why Prices Need Algorithms

In recent years we have seen many results showing computational hardness of computing equilibria. But in Tim’s EC 2015 paper with Inbal Talgam-Cohen (which won the best student paper award) they showed a surprising connection between computational complexity and the question whether an equilibrium exists at all. It is the latter type of question that is often of most interest to economists, and the paper also gives some “barrier results” to resolving open questions in economics.

 

Wim Martens: Optimizing Tree Pattern Queries: Why Cutting Is Not Enough

Tree patterns are a natural (and practically used) formalism for queries about tree-shaped data such as XML documents. Wim will talk about some new insights on these patterns. It is rare that the counterexample for a 15-year old conjecture is small enough to print on a T shirt, but in Wim’s  PODS 2016 paper with Czerwinski, Niewerth, and Parys (which was presented in the awards session and also chosen as SIGMOD highlight) they were able to do just that. (Wim did not tell me if the shirts would be available for sale in the conference..)

 

Wednesday, June 21, 4:15pm-5:30pm

Atri Rudra: Answering FAQs in CSPs, Probabilistic Graphical Models, Databases, Logic and Matrix operations

The Functional Aggregate Query (FAQ) problem generalizes many tasks studied in a variety of communities including solving constraint-satisfaction problems, evaluating database queries, and problems arising in probabilistic graphical models, coding theory, matrix chain computation, and the discrete Fourier transform. In Atri’s PODS 2016 paper with Abo Khamis and Ngo (which won the best paper award and was selected as SIGMOD highlight), they unified and recovered many old results in these areas, and also obtained several new ones.

 

Vasilis Syrgkanis: Fast convergence of learning in games

Vasilis will talk on some recent works on the interface of learning theory and game theory. Specifically, he will discuss how natural learning algorithms converge much faster than expected (e.g., at a rate of  instead of the classical  )  to  the optimum of various games. This is based on his NIPS 2015 paper with Agarwal, Luo, and Schapire, which won the best paper award.

 

Chris Umans: On cap sets and the group-theoretic approach to matrix multiplication

Chris will discuss the recent breakthroughs on the “cap set problem” and how they led to surprising insights on potential matrix-multiplication algorithms.  Based on this Discrete Analysis paper with Blasiak, Church, Cohn, Grochow, Naslund,  and Sawin.

 

Thursday, June 22, 3:50pm-5:30pm

Christopher Ré: Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling

Gibbs sampling is one of the most natural Markov Chains arising in many practical and theoretical contexts, but practically running the algorithm is very expensive. The Hogwild! Framework of Chris and co authors is a way to run such algorithms in parallel without locks but it’s unclear that the output distribution is still correct. In Chris’s  ICML 2016 paper with De Sa and Olukotun (which won the best paper award) they gave the first theoretical analysis of this algorithm.

 

Nate Foster: The Next 700 Network Programming Languages

I never expected to see Kleene Algebra, straight from the heart of Theory B,  used for practical packet processing in routers, but this is exactly what was done by this highly influential POPL 2014 paper of Nate with Anderson, Guha, Jeannin, Kozen, Schlesinger, and Walker.

 

Mohsen Ghaffari:  An Improved Distributed Algorithm for Maximal Independent Set

Maximal Independent Set is the “crown jewel of distributed symmetry breaking problems“  to use the words from the 2016 Dijkstra prize citation for the works showing an  time distributed algorithm. In Mohsen’s SODA 2016 paper (which won the best paper award) he improved on those works to give a local algorithm where each vertex will finish the computation in time that is . Moreover, in graphs with degree , all nodes will terminate faster than the prior algorithms, in particular almost matching the known lower bound.

 

Valeria Nikolaenko:  Practical post-quantum key agreement from generic lattices

With increasing progress in quantum computing, both the NSA and commercial companies are getting increasingly nervous about the security of RSA, Diffie-Hellman, and Elliptic Curve Crypto. Unfortunately, lattice-based crypto, which is the main candidate for “quantum resistant” public key encryption, was traditionally not efficient enough to be used in real world web security. This has been changing with recent works. In particular in Valeria’s  ACM CCS 2016 paper with Bos et al they gave a practical scheme based on standard computational assumptions on lattices. This is a follow up to the New Hope cryptosystem which is currently implemented in Chrome canary.