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.

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.

Amnon gave a highly intuitive talk that focused on the analysis, and I wish to complement it by spelling out the construction. One way to describe it is as a variant on the Zig-Zag/Replacement product, except that here we combine a large $DS-regular expander graph with a small $D^t$-vertex $d$-regular expander graph, where as usual $d << D$ but here $t>1$ (rather than $t=1$ as usual). In addition, we use functions $M:[D^t]\to[D]$ and $P:[D^t]\to[D^t]$ in order to map labels of vertices of the small graph to moves on the large graph, and to permute the labels of the small graph. Specifically, viewing $[D^t] = [D]^t$, Amnon lets $M$ take the first element in a $t$-sequence and $P$ be a cyclic shift of such a sequence. The $\eps$-bias space is obtained by starting with an $\eps_0$-bias space, for some small constant $\eps_0>0$, and associating its elements with the vertices of the composed graph. Taking a random walk on this expander we output the XOR of the labels of the vertices visited.

Avi Wigderson: On the Nature and Future of ToC

The core of Avi's invited (keynote) lecture was spelling out the nature of ToC. Avi stressed that TOC is a distinct scientific discipline that is focused on a fundamental agenda that is central to the agenda of many scientific disciplines. Rather than enumerating these disciplines, I would say that for several centuries the model of a mechanical process, where mechanical is opposed to living and willing, has dominated the human perception of the world. In particular, mechanical models are dominant in all scientific disciplines. From that perspective, the general rules that govern mechanical processes of various types are central to all these disciplines, and the investigation of these rules is what TOC is about.

While not each of us can deliver an exposition of the type delivered by Avi, we can and should all recognize and fully internalize the verity of the main message he communicated. Such an internalization will project the sense of importance of TOC even if we don't communicate it explicitly and elaborately. For sure, we should stop portraying ourselves as supposedly playing useless games.

Non-Interactive Delegation and Batch NP Verification from Standard Computational Assumptions by Zvika Brakerski, Justin Holmgren, and Yael Tauman Kalai

The main result is an adaptive and non-interactive argument system for any set in P in the public-key infrastructure model. Its computational-soundness is based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g., DDH, QR, or LWE).

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

In a clear and informative exposition, Alon provided the perspective of the statistics community on the problem of estimating unknown distributions. The performance of an algorithm $A$ wrt target distribution $p$ is defined as the expected distance between $p$ and the distribution output by $A$ when given samples of $p$, where the distance measure may vary (e.g., Norm2 is popular among engineers but quite useless here, and Norm1 or KL should be preferred). Classical work seems to focus on a fixed domain and a varying number of samples, but currently they also considering varying domain sizes. One such algorithm merely outputs the empirical probability, but it performs quite poorly. Other algorithms try to find the probability that is (among the) most likely given the empirical data (i.e., the samples provided).

This specific work (presented first in NIPS 2015) suggest to measure the performance of these algorithms by comparing their performance to the performance of the best algorithm that is given the histogram of the target distribution (i.e., given the distribution up to relabeling). It is shown that the error of a variant of the Good-Turing algorithm exceeds the optimal error by a function that is a negative power of the number of samples, and such a type of performance is the best possible.

Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace by William Hoza and Chris Umans

This paper addresses the question of whether derandomization of a randomized complexity class implies a pseudorandom generator (PRG) that suffices for such a derandomization. This question is studied in the context of space-bounded computation, where the known results exhibit a gap between derandomization and PRG constructions. It shows that such a gap is inherent to our state of knowledge in the sense that every overhead-free translation of derandomization to PRGs will imply that BPL is almost in L.

On the Complexity of Local Distributed Graph Problems by Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus

This paper studies the complexity gap between the known randomized and deterministic algorithms for some natural graph problems (e.g., MIS and (degree+1)-coloring) in the LOCAL model of distributed computing. This is done by introducing a rather fictitious model, called SLOCAL, presenting complete (in an adequate sense) problems in it (i.e., problems that have polylogarithmic complexity in it), and presenting a complete problem that is trivial for randomized algorithms (in LOCAL). Hence, this problem may be viewed as the core difficulty in getting efficient deterministic algorithms (in LOCAL), where efficiency is defined as having polylogarithmically many rounds of computation.

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

This paper refers to the program for proving upper bounds on the exponent, denoted omega, of matrix multiplication based on potential results regarding group algebra multiplication [Cohen and Umans, 2003]. More specifically, it refers to conjectures proposed by Cohn, Kleinberg, Szegedy, and Umans (in 2005) towards showing that omega is 2. The current work (published in Discrete Analysis) shows that this cannot be done using Abelian groups of bounded exponent. Although negative results regarding the program keep being found, its devoted researchers maintain their optimism, viewing these negative results as directives to the right way. I cannot but admire their persistence and keep my fingures crossed for them.

Orna Kupferman: Examining classical graph-theory problems from the viewpoint of formal-verification methods

Orna surveyed a host of computational problems regarding graphs that emerge naturally from formal-verification applications. Three main classes of problems are:
  1. Generalizations of classical graph theoretic problems obtained by considering edge labels. For example, one may search for shortest, Eulerian, or Hamiltonian paths among all paths that satisfy a predetermined condition regarding the sequence of labels that correspond to the edges on the path. Such a condition may be specified by a regular expression or by a more expressive formalism.
  2. Generalizations of classical graph theoretic problems into games in which an adversary controls some of the vertices (or edges). For example, max-flow can be generalized such that, at adversary-controlled vertices, a legal worst-case (rather than best) assignment of the arriving flow to the outgoing edges is selected.
  3. Classical graph theoretic problems regarding graphs that are given by succinct representation, where the succinct representation is given by a hierarchical structure (which specifies an iterative construction in which boxes in one super-graph are replaced by designated super-graphs).

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

For an unknown string $x$, one obtains a sequence of samples such that each sample is obtained by deleting each character in $x$ with a fixed probability, independently of all other events. This work shows that $exp(O(n^{1/3}))$ samples are necessary and sufficient when using a specific algorithm. The algorithm, which I find quite unnatural, first determines a probability sequence $p$ such that the $i$th bit in $p$ equals the that the $i$th bit in a given sample equals 1, and then determines $x$ according to the maximum likelihood principle.

Time-Space Hardness of Learning Sparse Parities by Gillat Kol, Ran Raz, and Avishay Tal

Generalizing a result of Raz (2016), it is shown that, for every $\ell$ smaller than $n^{0.9}$, learning $\ell$-linear functions requires either $\Omega(n\cdot\ell^{0.99})$ memory or more than $\exp(\Omega(\ell\log\ell))$ samples. For every $\ell$ smaller than $n/2$, it also holds that learning $\ell$-linear functions requires either $\Omega(n\cdot\ell)$ memory or more than $\exp(\Omega(\ell))$ samples.

Addition is Exponentially Harder than Counting for Shallow Monotone Circuits by Xi Chen, Igor Oliveira, and Rocco Servedio

The issue is comparing the complexity of computing a threshold function with exponentially large weights versus doing so when the weights are of polynomial size (or unit weights, by duplication). While it is known that a circuit with exponentially large weights can be emulated by a circuit with no weights by increasing the depth by one unit, this construction introduces negation gates. It is shown that the use of negation is inherent, since a single gate that computes $d$-way threshold with large weights requires depth $d$ monotone circuits of size $\exp(\Omega(n^{1/d}))$.

An Improved Distributed Algorithm for Maximal Independent Set by Mohsen Ghaffari

The MIS is a central problem in this model, as exemplified by the fact that many other problems reduce to it. For example, maximal matching is reduced to MIS (by the line graph), whereas $d+1$-vertex coloring is reduced to MIS (by Cartesian product with the $d+1$-Clique), where $d$ is a bound on vertex degrees. The focus of this work is on the randomized complexity of computing MIS in the LOCAL model, where $n$ denotes the number of vertices.

Improving over the classical results of Luby and Alon, Babai and Itai, the current paper (presented in SODA 2016) provides an algorithm of complexity $O(log d)+\exp(O(loglog n))$. The general strategy consists of two steps. First, $O(\log d)$ rounds are used in order to ``shatter'' the graph to connected components of polylogarithmic size. This step is randomized and succeeds with very high probability; it cannot be recursed, since we need to care of an almost linear number of different events (whereas the round complexity is related both to the degree and to the desired error bound). The second stage applies the know deterministic algorithm (of complexity $\exp(\sqrt(\log s))$ for $s$-vertex graphs) to each of the connected components.

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.