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)