| Abstract |
This section of SICOMP contains 11 specially selected papers from the Forty-seventh Annual ACM Symposium on Theory of Computing, otherwise known as STOC 2015, held June 15 to 17 in Portland, Oregon. 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 Ronitt Rubinfeld (chair), Benny Applebaum, Niv Buchbinder, Edith Cohen, Costis Daskalakis, Ilias Diakonikolas, Shaddin Dughmi, Michael Forbes, Michel Goemans, Elena Grigorescu, Venkatesan Guruswami, Bernhard Haeupler, Sandy Irani, Yael Kalai, Sanjeev Khanna, Swastik Kopparty, Krzysztof Onak, Anup Rao, Ben Reichardt, Yaron Singer, Nikhil Srivastava, Chris Umans, Ola Svensson, Jonathan Ullman, Udi Wieder, and Mary Wootters. We briefly describe the papers that appear here. Sketching and Embedding Are Equivalent for Norms, by Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn, provides an almost complete characterization of sketching in terms of embeddings for normed spaces. Inapproximability of Nash Equilibrium, by Aviad Rubinstein, proves that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for some constant value of $\epsilon$ in multiplayer games with binary strategies and sparse player interactions, where each player's payoff depends on the strategy of at most three other players; this resolves an open problem of about a decade on the complexity of approximate Nash equilibrium. Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, by Siddharth Barman, provides a self-contained proof of an approximate version of Carathéodory's theorem for $p$-norm approximating vectors in a polytope of bounded $p$-norm vectors via a convex combination of a dimension-independent number of polytope vertices, along with algorithmic applications of this theorem, including a polynomial-time approximation scheme for Nash equilibrium in two-player games with fixed column sparsity, and an additive approximation algorithm for the normalized densest $k$-subgraph problem. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing, by Scott Aaronson and Andris Ambainis, achieves essentially the largest possible separation between quantum and classical query complexities using a property-testing problem called Forrelation. On the Lovász Theta Function for Independent Sets in Sparse Graphs, by Nikhil Bansal, Anupam Gupta and Guru Prashanth Guruganesh, shows that the integrality gap of the Lovász $\vartheta$-function is $\tilde{O}(d/\log^2 d)$. Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, by Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam, considers an online version of the Submodular Welfare Maximization problem and shows that the greedy algorithm obtains a competitive ratio of at least .505 in the random order model. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False), by Arturs Backurs and Piotr Indyk, shows that if the edit distance between two strings can be computed in time $O(n^{2-\delta})$ for some constant $\delta > 0$, then the strong exponential time hypothesis would be violated. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, by Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu, obtains novel lower bounds under the assumption that at least one of the 3-SUM, APSP, and CNF-SAT hypotheses are true. Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings, by Nir Bitansky, Ran Canetti, Sanjam Garg, Justin Holmgren, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang, and Vinod Vaikuntanathan, shows a novel use of an indistinguishability obfuscation (iO) for circuits to construct a succinct randomized encoding scheme, and an iO for RAM programs; prior to this work, there were no candidates for either of these two primitives. Approximating the Nash Social Welfare with Indivisible Items, by Richard Cole and Vasilis Gkatzelis, provides the first efficient constant-factor approximation algorithm for the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents valuations, also called the Nash social welfare. Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, by Ben Cousins and Santosh Vempala, gives a $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$, as well as an $O^*(n^3)$ algorithm for computing the Gaussian volume of a convex set that contains the unit ball. The following paper was also invited to the special section but remains in review at this writing. If accepted, it will appear in a later SICOMP issue. Randomized Composable Core-Sets for Distributed Submodular Maximization, by Vahab Mirrokni and Morteza Zadimoghaddam, shows how a randomized version of composable core-sets can beat impossibility results for the deterministic version on coverage, monotone, and non-monotone submodular maximization problems. We thank the authors and the program committee for their hard work, and we especially thank the reviewers for their work in evaluating and improving the submitted papers. |
