Special Section on the Forty-Fifth Annual ACM Symposium on the Theory of Computing (STOC 2013)
James Aspnes, Yuval Ishai, Peter Bro Miltersen · SIAM Journal on Computing · 2016
This issue of SICOMP contains seven specially selected papers from STOC 2013, the Forty-Fifth Annual ACM Symposium on the Theory of Computing, which was held June 1 through 4, 2013, in Palo Alto, California. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough the reviewing process of SICOMP. The program committee for STOC 2013 consisted of an executive committee made up of Boaz Barak, Irit Dinur, Leslie Goldberg, Giuseppe F. Italiano, Sampath Kannan, Neeraj Kayal, Michael Mitzenmacher, and Miklos Santha, supervising a broader program committee made up of Scott Aaronson, Susanne Albers, Benny Applebaum, James Aspnes, Per Austrin, Avrim Blum, Anne Broadbent, Peter Bürgisser, John Byers, Amit Chakrabarti, Shuchi Chawla, Bernard Chazelle, Xi Chen, Julia Chuzhoy, Graham Cormode, Artur Czumaj, Constantinos Daskalakis, Zeev Dvir, Jeff Erickson, Lance Fortnow, Craig Gentry, Anna Gilbert, Sudipto Guha, Mohammed Taghi Hajiaghayi, Moritz Hardt, Avinatan Hassidim, Monika Henzinger, Maurice Herlihy, Nicole Immorlica, Russell Impagliazzo, Piotr Indyk, Yuval Ishai, Mark Jerrum, Yael Kalai, Tali Kaufman, Haim Kaplan, Jonathan Kelner, Valerie King, Samir Khuller, Robert Kleinberg, Elias Koutsoupias, Robert Krauthgamer, Pinyan Lu, Aleksander Madry, Dániel Marx, Peter Bro Miltersen, Moni Naor, Ilan Newman, Rina Panigrahy, Prasad Raghavendra, Andrea Richa, Michael Schapira, Rocco Servedio, Amir Shpilka, Cliff Stein, David Steurer, Mikkel Thorup, Virginia Vassilevska Williams, Eric Vigoda, Ryan Williams, Ronald de Wolf, and David Zuckerman. The program chair was Joan Feigenbaum. Included in this issue are the following papers: ``An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube," by Deeparnab Chakrabarty and C. Seshadhri, provides a randomized tester for near-monotone functions requiring sublinear queries. ``Answering $n^{2+o(1)}$ Counting Queries with Differential Privacy Is Hard," by Jonathan Ullman, gives a nearly tight bound on the number of counting queries that can be answered while preserving privacy. ``Natural Proofs Versus Derandomization," by Ryan Williams, demonstrates surprising connections between natural proofs, derandomization, and weak circuit lower bounds. ``Approximating $k$-median via Pseudo-Approximation," by Shi Li and Ola Svensson, improves the approximation ratio for $k$-median from $3+\epsilon$ to $1 + \sqrt{3} + \epsilon$, the first improvement in a decade. ``Maintaining Shortest Paths under Deletions in Weighted Directed Graphs," by Aaron Bernstein, improves on previous algorithms for maintaining all-pairs approximate shortest paths. ``The Geometry of Differential Privacy: The Sparse and Approximate Cases," by Aleksandar Nikolov, Kunal Talwar, and Li Zhang, characterizes the trade-offs between accuracy and privacy for a rich class of database queries. ``Superlinear Advantage for Exact Quantum Algorithms," by Andris Ambainis, gives the first example of a function that can be computed with a sublinear number of queries compared to the corresponding deterministic algorithm. We thank the authors, the STOC 2013 program committee, the STOC 2013 external reviewers, and the SICOMP referees for all of their hard work.