## A report from the 49th STOC (and Theory Fest 2017)

Held in Montreal, June 19-23, 2017.

My impression is that the Theory-Fest/STOC17 (see program) was very successful.

I must confess that I was originally skeptical wrt the general idea as well as some specific aspects of it, and attended the event only because I was required to give a lecture. Still, I must admit I was wrong. I especially liked the idea of three parallel sessions coupled with few talks in a plenary session, but I would have suggested to have more (say 10-15) presentations of STOC papers rather than only 3+1 "best papers". Also, the presented papers need not be "best" (per merits) but rather "most adequate for a plenary session" per the appeal of what can be presented in a short talk. I also liked the idea of presentation of papers that appeared in other conferences (esp., CCC, SODA, PODC, ML/NIPS, TCC etc) or even ("heavens forbid") only in journals. The tutorials and workshops also seem to add a lot, and I am told that the same holds wrt the poster sessions (although having them at the night of a full day strikes me as too excessive).

Following are some of the lecture I have heard and got most from.

• Explicit, Almost Optimal, Epsilon-Balanced Codes by Amnon Ta-Shma.
• Avi Wigderson: On the Nature and Future of ToC
• Non-Interactive Delegation and Batch NP Verification from Standard Computational Assumptions by Zvika Brakerski, Justin Holmgren, and Yael Tauman Kalai.
• Competitive Distribution Estimation: Why is Good-Turing Good by Alon Orlitsky
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace by William Hoza and Chris Umans.
• On the Complexity of Local Distributed Graph Problems by Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus.
• On cap sets and the group-theoretic approach to matrix multiplication by Chris Umans
• Orna Kupferman: Examining classical graph-theory problems from the viewpoint of formal-verification methods
• Optimal Mean-based Algorithms for Trace Reconstruction (using $exp(O(n^{1/3}))$ Samples) by Anindya De, Ryan O'Donnell, Rocco Servedio, Fedor Nazarov, and Yuval Peres.
• Time-Space Hardness of Learning Sparse Parities by Gillat Kol, Ran Raz, and Avishay Tal
• Addition is Exponentially Harder than Counting for Shallow Monotone Circuits by Xi Chen, Igor Oliveira, and Rocco Servedio
• An Improved Distributed Algorithm for Maximal Independent Set by Mohsen Ghaffari
• Workshop on Probabilistically checkable and interactive proofs (PCP/IP): Between theory and practice (organized by Eli Ben-Sasson, Alessandro Chiesa, and Yuval Ishai)
Note that I did not list works that appeared in prior posts of mine (e.g., Nr. 217).

While I do not like the idea of trying to predict the future of TOC or trying to direct it by some authoritative advice, I found some comments made in the panel TCS - the Next Decade well taken. In particular, Cynthia Dwork highlighted the inspiration provided to the study of differential privacy by past theoretical research in cryptography (although the former had to make a significant deviation from the mind-set of the latter). Ankur Moitra highlighted the ToC tradition of differentiating between models and algorithms, and the willingness to develop both in a slow and creative manner, while noting that such an attitude is lacking in some engineering disciplines. Tim Roughgarden added that core ToC tends not to care about specific problems but rather uses them as a way to uncover more general phenomena and/or to discover new techniques. Russell Impagliazzo and Dan Spielman mused on the impression that practical researchers tend to view all problems as feasibly solvable.

#### Explicit, Almost Optimal, Epsilon-Balanced Codes by Amnon Ta-Shma

The goal of obtaining an explicit construction of small biased sample spaces of optimal size is equivalent to obtaining explicit constructions of linear codes with optimal rate when all nonzero codewords have Hamming weight close to half. In the first case we desire sample spaces of size $n=O(k/\eps^2)$ for length $k$ and bias $\eps$, and in the second case we seek block-length $n$ (where $k/n$ is the rate of the code) and relative weights that are $\eps$-close to 1/2.

#### Workshop on Probabilistically checkable and interactive proofs (PCP/IP): Between theory and practice (organized by Eli Ben-Sasson, Alessandro Chiesa, and Yuval Ishai)

This workshop provided several surveys of the relevant theory and the considerations in trying to transport them to practice. Regarding the latter issue, Justin Thaler provided a survey of the four common approaches that underly these attempts, whereas a fifth approach pivoted at Interactive Oracle Proofs (aka Probabilistically Checkable Interactive Proofs) was surveyed by Alessandro Chiesa (and also by Eli Ben-Sasson). The four approaches are (1) Linear PCPs + crypto implying SNARKs (which are typically zero-knowledge), where SNARK stands for succinct non-interactive arguments of knowledge; (2) IP based schemes (a la [GKR]), (3) short PCPs, and (4) MPC in the head and garbled circuits Most implementation attempts follow approaches (1) and (2), and there are lots of them.

Back to list of Oded's choices.