Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018)
Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas · SIAM Journal on Computing · 2020
This issue of SICOMP contains 10 specially selected papers from the Fiftieth Annual ACM Symposium on Theory of Computing, otherwise known as STOC 2018, held June 25 to 29 in Los Angeles, California. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee consisted of Dimitris Achlioptas (University of California, Santa Cruz), Dorit Aharonov (Hebrew University), Susanne Albers (Technical University Munich), Eric Allender (Rutgers University), Sayan Bhattacharya (University of Warwick), Richard Cole (New York University), Vitaly Feldman (Google Research), Uriel Feige (Weizmann Institute), Sanjam Garg (University of California, Berkeley), Ashish Goel (Stanford University), Parikshit Gopalan (VMware), Monika Henzinger, chair (University of Vienna), Giuseppe Italiano (Luiss University), Robert Kleinberg (Cornell University), Claire Matthieu (École Normale Supérieure, CNRS), Ankur Moitra (Massachusetts Institute of Technology), Danupon Nanongkai (KTH Royal Institute of Technology, Stockholm), Michał Pilipczuk (University of Warsaw), Krzysztof Pietrzak (Institute of Science and Technology, Austria), Aaron Sidford (Stanford University), Christian Sohler (Universität zu Köln), Prasad Tetali (Georgia Institute of Technology), Kunal Talwar (Apple), Luca Trevisan (Bocconi University), Thomas Vidick (California Institute of Technology), Emo Welzl (ETH Zurich), Philipp Woelfel (University of Calgary), David Woodruff (Carnegie Mellon University), and Mary Wootters (Stanford University). They selected 112 papers out of 416 submissions. We briefly describe the papers that appear here. In “Round Compression for Parallel Matching Algorithms,” Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski break the $O(\log n)$ round complexity bound for 2-approximating the maximum matching in near-linear memory regime of the massively parallel computation model. In “Smooth Heaps and a Dual View of Self-Adjusting Data Structures,” László Kozma and Thatchaphol Saranurak show a new correspondence between self-adjusting binary search trees (BSTs) and heaps. Using this connection they are able to transfer known lower bounds on BSTs to a general model of heaps as well as obtain a new, simple, and efficient heap algorithm called the “smooth heap.” In “Collusion Resistant Traitor Tracing from Learning with Errors," Rishab Goyal, Venkata Koppula, and Brent Waters introduce a new approach to the traitor tracing problem. Informally, in traitor tracing one aims to devise an encryption scheme such that decryption can be performed using $n$ different private keys and such that moreover any decryption can be “traced back" to the key(s) that was or were used for it. In this paper the authors obtain the first scheme with ciphertext size that grows polynomially in $\log(n)$ and the security parameter $\lambda$ and whose security is based on the learning with errors assumption. In “Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs,” Mark Braverman, Gil Cohen, and Sumegha Garg construct a hitting set for unrestricted read-once branching programs with seed length $O(\log^2n + \log(1/\varepsilon))$. This is the first improvement since Nisan's pseudorandom generator with seed length $O(\log^2n + \log n \log(1/\varepsilon)$. In “Circuit Lower Bounds for Nondeterministic Quasi-Polytime from a New Easy Witness Lemma,” Cody Murray and Ryan Williams show that if every problem in NP has polynomial-size circuits for a fixed polynomial, then every problem in NP also has a fixed polynomial-size witness. A specific consequence of this result is that for every fixed $k$, NQP does not have $n^{\log^k n}$-size ACC$\circ$THR circuits. In “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds,” Kasper Green Larsen, Omri Weinstein, and Huacheng Yu prove the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean data structure problems, a long-standing milestone in data structure lower bounds. In “Shadow Tomography of Quantum States,” Scott Aaronson asks: Given an unknown $D$-dimensional quantum mixed state $\rho$ and two-outcome measurements $E_1, \ldots, E_M$, how many copies of $\rho$ are needed to estimate the probability that $E_i$ accepts $\rho$ to within additive error $\varepsilon$, for each of the $M$ measurements? He shows that $O(\varepsilon^{-4} \log^4 M \log D)$ copies of $\rho$ suffice, implying, for example, that we can learn the behavior of an arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only $n^{O(1)}$ copies of the state. In “Inapproximability of the Independent Set Polynomial in the Complex Plane,” Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič study the complexity of approximating the independent set polynomial of a graph with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. They prove that outside a cardioid-shaped region in the complex plane identified by Peters and Regts, wherein the occupation ratios of $\Delta$-regular trees converge, approximation is $\#$P-hard (unless $\lambda$ is a positive real number, in which case it is NP-hard). In “A Friendly Smoothed Analysis of the Simplex Method,” Daniel Dadush and Sophie Huiberts consider linear programs with $d$ variables and $n$ constraints, smoothed by the addition of Gaussian noise with variance $\sigma^2$. They provide an improved and greatly simplified analysis of shadow simplex methods by combining an improved shadow bound with improvements on algorithmic techniques of Vershynin and show that in expectation $O(d^2 \sqrt{\log n} \, \sigma^{-2} + d^3 \log^{3/2}n)$ pivots suffice. In “Nearly Work-Efficient Parallel Algorithm for Digraph Reachability,” Jeremy T. Fineman presents a randomized parallel algorithm for digraph reachability and related problems with expected work $\tilde{O}(m)$ and span $\tilde{O}(n^{2/3})$. This is the first parallel algorithm having both nearly linear work and strongly sublinear span.