The co-winners of the STOC 2013 Best-Paper Award are:
"Low Rank Approximation and Regression in Input Sparsity Time," by Ken Clarkson and David Woodruff
and
"Approximation Resistance from Pairwise Independent Subgroups," by Siu On Chan.
The co-winners of the STOC 2013 Best-Student-Paper Award are:
"Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs," by Aaron Bernstein
and
"Approximation Resistance from Pairwise Independent Subgroups," by Siu On Chan.
List of accepted papers
Max flows in O(nm) time or less
James Orlin (MIT)
Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Hammurabi Mendes (Brown University) and Maurice Herlihy (Brown University)
Non-Black-Box Simulation in the Fully Concurrent Setting
Vipul Goyal (Microsoft Research, India)
Approximation Resistance from Pairwise Independent Subgroups
Siu On Chan (UC Berkeley)
Average-Case Lower Bounds for Formula Size
Ilan Komargodski (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)
New Independent Source Extractors with Exponential Improvement
Xin Li (University of Washington)
Random Lattice Triangulations: Structure and Algorithms
Pietro Caputo (University of Rome III), Fabio Martinelli (University of Rome III), Alistair Sinclair (UC Berkeley), and Alexandre Stauffer (University of Rome III)
The Complexity of Non-Monotone Markets
Xi Chen (Columbia University), Dimitris Paparas (Columbia University), and Mihalis Yannakakis (Columbia University)
Optimal Euclidean spanners: really short, thin and lanky
Michael Elkin (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)
Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
Xiangrui Meng (Stanford University) and Michael W. Mahoney (Stanford University)
Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data
Nir Bitansky (Tel Aviv University), Ran Canetti (Boston University and Tel Aviv University), Alessandro Chiesa (MIT), and Eran Tromer (Tel Aviv University)
Sparsity lower bounds for dimensionality reducing maps
Jelani Nelson (Institute for Advanced Study) and Huy L. Nguyen (Princeton University)
Approximating k-Median via Pseudo-Approximation
Shi Li (Princeton University) and Ola Svensson (EPFL)
Byzantine Agreement in Polynomial Expected Time
Valerie King (University of Victoria) and Jared Saia (University of New Mexico)
Equivalence of Deterministic One-Counter Automata is NL-complete
Stanislav Bohm (Technical University of Ostrava), Stefan Goller (University of Bremen), and Petr Jancar (Technical University of Ostrava)
Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard
Jonathan Ullman (Harvard University)
Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond
Shafi Goldwasser (MIT), Yael Kalai (Microsoft Research, New England), Raluca Ada Popa (MIT), Vinod Vaikuntanathan (University of Toronto), and Nickolai Zeldovich (MIT)
Lower bounds for RAMs and quantifier elimination
Miklos Ajtai (IBM Almaden Research Center)
New Bounds on Matching Vector Families
Abhishek Bhowmick (University of Texas at Austin), Zeev Dvir (Princeton University), and Shachar Lovett (UC San Diego)
The complexity of finite-valued CSPs
Johan Thapper (Universite Paris-Sud 11) and Stanislav Zivny (University of Warwick)
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time
Philip N. Klein (Brown University), Shay Mozes (MIT), and Christian Sommer (MIT)
Inverting well-conditioned matrices in Quantum Logspace
Amnon Ta-Shma (Tel-Aviv University)
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound
Venkatesan Guruswami (Carnegie Mellon University) and Chaoping Xing (Nanyang Technological University)
Quasipolynomial-time Canonical Form for Steiner Designs
Laszlo Babai (University of Chicago) and John Wilmes (University of Chicago)
Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma
David G. Harris (University of Maryland) and Aravind Srinivasan (University of Maryland)
Low Rank Approximation and Regression in Input Sparsity Time
Kenneth L. Clarkson (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)
Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Aaron Bernstein (Columbia University)
A o(n) monotonicity tester for boolean functions over the hypercube
Deeparnab Chakrabarty (Microsoft Research, India) and C. Seshadhri (Sandia National Laboratories, Livermore)
On the list decodability of random linear codes with large error rates
Mary Wootters (University of Michigan)
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled (University of Illinois at Urbana Champaign) and Benjamin Raichel (University of Illinois at Urbana Champaign)
Every locally characterized affine-invariant property is testable
Arnab Bhattacharyya (DIMACS), Eldar Fischer (Technion), Hamed Hatami (McGill), Pooya Hatami (University of Chicago), and Shachar Lovett (UC San Diego)
Superlinear advantage for exact quantum algorithms
Andris Ambainis (University of Latvia)
Efficient rounding for the noncommutative Grothendieck inequality
Assaf Naor (New York University), Oded Regev (New York University), and Thomas Vidick (MIT)
A node-capacitated Okamura-Seymour theorem
James R. Lee (University of Washington), Manor Mendel (Open University), and Mohammad Moharrami (University of Washington)
Lee-Yang Theorems and the Complexity of Computing Averages
Alistair Sinclair (UC Berkeley) and Piyush Srivastava (UC Berkeley)
Beyond Worst-Case Analysis in Private Singular Vector Computation
Moritz Hardt (IBM Almaden Research) and Aaron Roth (University of Pennsylvania)
Classical Hardness of Learning with Errors
Zvika Brakerski (Stanford University), Adeline Langlois (ENS de Lyon), Chris Peikert (Georgia Tech), Oded Regev (New York University), and Damien Stehle (ENS de Lyon)
Coevolutionary Opinion Formation Games
Kshipra Bhawalkar (Stanford University), Sreenivas Gollapudi (Microsoft Research, Silicon Valley), and Kamesh Munagala (Duke University)
Predicate Encryption for Circuits
Sergey Gorbunov (University of Toronto), Vinod Vaikuntanathan (University of Toronto), and Hoeteck Wee (George Washington University)
On the complexity of Trial and Error
Xiaohui Bei (Nanyang Technological University), Ning Chen (Nanyang Technological University), and Shengyu Zhang (The Chinese University of Hong Kong)
Fast Routing Table Construction Using Small Messages [Extended Abstract]
Christoph Lenzen (Weizmann Institute of Science) and Boaz Patt-Shamir (Tel Aviv University)
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas
Manindra Agrawal (Indian Institute of Technology, Kanpur), Chandan Saha (Indian Institute of Science), and Nitin Saxena (Hausdorff Center for Mathematics)
Explicit Lower Bounds via Geometric Complexity Theory
Peter Burgisser (University of Paderborn) and Christian Ikenmeyer (University of Paderborn)
Shielding circuits with groups
Eric Miles (Northeastern University) and Emanuele Viola (Northeastern University)
Extending continuous maps: polynomiality and undecidability
Martin Cadek (Masaryk University Brno), Marek Krcal (Charles University Prague), Jiri Matousek (Charles University Prague and ETH Zurich), Lukas Vokrinek (Masaryk University Brno), and Uli Wagner (EPFL)
Testing Subdivision-Freeness: Property Testing Meets Structural Graph Theory
Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO Kawarabayashi Project) and Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)
Some Trade-off Results for Polynomial Calculus
Chris Beck (Princeton University), Jakob Nordstrom (KTH Royal Institute of Technology), and Bangsheng Tang (Tsinghua University)
Going After the k-SAT Threshold
Amin Coja-Oghlan (Goethe University) and Konstantinos Panagiotou (University of Munich)
Composable and Efficient Mechanisms
Vasilis Syrgkanis (Cornell University) and Eva Tardos (Cornell University)
Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Yun Kuen Cheung (New York University), Richard Cole (New York University), and Nikhil Devanur (Microsoft Research, Redmond)
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat (Brown University) and Philip N. Klein (Brown University)
The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
Albert Gu (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), and Amit Kumar (Indian Institute of Technology, Delhi)
On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
Anupam Gupta (Carnegie Mellon University), Kunal Talwar (Microsoft Research, Silicon Valley), and David Witmer (Carnegie Mellon University)
Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
Deeparnab Chakrabarty (Microsoft Research, India), C. Seshadhri (Sandia National Labs, Livermore), and Deeparnab Chakrabarty (Microsoft Research, India)
On the Concrete Efficiency of Probabilistically Checkable Proofs
Eli Ben-Sasson (Technion and MIT), Alessandro Chiesa (MIT), Daniel Genkin (Technion), and Eran Tromer (Tel Aviv University)
Polynomial-time perfect matchings in dense hypergraphs
Peter Keevash (Queen Mary, University of London), Fiachra Knox (Queen Mary, University of London), and Richard Mycroft (University of Birmingham)
Large-Treewidth Graph Decompositions and Applications
Chandra Chekuri (University of Illinois at Urbana-Champaign) and Julia Chuzhoy (Toyota Technological Institute, Chicago)
Differential Privacy for the Analyst via Private Equilibrium Computation
Justin Hsu (University of Pennsylvania), Aaron Roth (University of Pennsylvania), and Jonathan Ullman (Harvard University)
Succinct Sampling from Discrete Distributions
Karl Bringmann (Max Planck Institute for Informatics) and Kasper Green Larsen (MADALGO, Aarhus University)
The Orbit Problem in Higher Dimensions
Ventsislav Chonev (Oxford University), Joel Ouaknine (Oxford University), and James Worrell (Oxford University)
Homomorphic Fingerprints under Misalignments
Alexandr Andoni (Microsoft Research, Silicon Valley), Assaf Goldberger (Tel Aviv University), Andrew McGregor (University of Massachusetts), and Ely Porat (Bar-Ilan University)
Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang (KTH Royal Institute of Technology)
An Information Complexity Approach to Extended Formulations
Mark Braverman (Princeton University) and Ankur Moitra (Institute for Advanced Study)
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
Niv Buchbinder (Tel Aviv University), Joseph (Seffi) Naor (Technion), and Roy Schwartz (Microsoft Research, Redmond)
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Daniel Kane (Stanford University) and Raghu Meka (Institute for Advanced Study and DIMACS)
Analysis of Spectral Partitioning through Higher Order Spectral Gap
Tsz Chiu Kwok (The Chinese University of Hong Kong), Lap Chi Lau (The Chinese University of Hong Kong), Yin Tat Lee (The Chinese University of Hong Kong), Shayan Oveis Gharan (Stanford University), and Luca Trevisan (Stanford University)
Quantum de Finetti Theorems under Local Measurements with Applications
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)
Stochastic Combinatorial Optimization via Poisson Approximation
Jian Li (IIIS, Tsinghua University) and Wen Yuan (IIIS, Tsinghua University)
Natural Proofs Versus Derandomization
Ryan Williams (Stanford University)
Majority is Stablest : Discrete and SoS
Anindya De (UC Berkeley), Elchanan Mossel (UC Berkeley), and Joe Neeman (UC Berkeley)
Combinatorial Walrasian Equilibrium
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)
Simultaneous Auctions are (almost) Efficient
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Hu Fu (Cornell University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)
The Geometry of Differential Privacy: The Sparse and Approximate Cases
Aleksandar Nikolov (Rutgers University), Kunal Talwar (Microsoft Research, Silicon Valley), and Li Zhang (Microsoft Research, Silicon Valley)
Delegation for Bounded Space
Yael Tauman Kalai (Microsoft Research, New England), Ran Raz (Weizmann Institute of Science), and Ron D. Rothblum (Weizmann Institute of Science)
A new family of locally correctable codes based on degree-lifted algebraic geometry codes
Eli Ben Sasson (Technion and MIT), Ariel Gabizon (Technion), Yohay Kaplan (Technion), Swatik Kopparty (Rutgers University), and Shubangi Saraf (Rutgers University)
Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum (Microsoft Research, Silicon Valley), Salil Vadhan (Harvard University), and Avi Wigderson (Institute for Advanced Studies)
How Robust are Linear Sketches to Adaptive Inputs?
Moritz Hardt (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)
The Approximate Rank of a Matrix and its Algorithmic Applications
Noga Alon (Tel Aviv University) and Santosh Vempala (Georgia Tech)
Communication Lower Bounds Using Directional Derivatives
Alexander A. Sherstov (UC Los Angelos)
Fast approximation algorithms for the diameter and radius of sparse graphs
Liam Roditty (Bar Ilan University) and Virginia Vassilevska Williams (UC Berkeley and Stanford University)
Product-state approximations to quantum ground states
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)
On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography
Nir Bitansky (Tel Aviv University) and Omer Paneth (Boston University)
THE LOSS OF SERVING IN THE DARK
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), and Iftah Gamzu (Tel Aviv University)
Tight Bounds for Online Vector Bin Packing
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), Seny Kamara (Microsoft Research, Redmond), and Bruce Shepherd (McGill University)
A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Jin-Yi Cai (University of Wisconsin at Madison), Heng Guo (University of Wisconsin at Madison), and Tyson Williams (University of Wisconsin at Madison)
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner (MIT), Lorenzo Orecchia (MIT), Aaron Sidford (MIT), and Zeyuan Allen Zhu (MIT)
Low-rank Matrix Completion using Alternating Minimization
Prateek Jain (Microsoft Research, India), Praneeth Netrapalli (The University of Texas at Austin), and Sujay Sanghavi (The University of Texas at Austin)
Multi-Stage Propagation and Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
Xi Chen (Columbia University), Xiaorui Sun (Columbia University), and Shang-Hua Teng (University of Southern California)
Strong ETH Holds For Regular Resolution
Chris Beck (Princeton University) and Russell Impagliazzo (UC San Diego)
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Vitaly Feldman (IBM Research Almaden), Elena Grigorescu (Purdue University), Lev Reyzin (University of Illinois at Chicago), Santosh Vempala (Georgia Tech), and Ying Xiao (Georgia Tech)
Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup (AT&T Labs-Research and University of Copenhagen)
Prior-Independent Mechanisms for Scheduling
Shuchi Chawla (University of Wisconsin at Madison), Jason D. Hartline (Northwestern University), David Malec (University of Wisconsin at Madison), and Balasubramanian Sivan (University of Wisconsin at Madison)
From information to exact communication
Mark Braverman (Princeton University), Ankit Garg (Princeton Unviersity), Denis Pankratov (University of Chicago), and Omri Weinstein (Princeton University)
Interactive Channel Capacity
Gillat Kol (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)
Fast Hamiltonicity checking via bases of perfect matchings
Marek Cygan (University of Warsaw), Stefan Kratsch (Max Planck Institute), and Jesper Nederlof (Utrecht University)
Witness Encryption and its Applications
Sanjam Garg (UC Los Angelos), Craig Gentry (IBM Watson Research Lab), Amit Sahai (UC Los Angelos), and Brent Waters (The University of Texas at Austin)
Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security
Kai-Min Chung (Cornell University), Rafael Pass (Cornell University), and Karn Seth (Cornell University)
A New Approach to Computing Maximum Flows using Electrical Flows
YinTat Lee (MIT), Satish Rao (UC Berkeley) and Nikhil Srivastava (Microsoft Research, India)