STOC 2013 Accepted Papers (with pdf files)

STOC 2013 accepted paper list is here. Following are PDF pointers to online versions.

————————————————————————————-

Max flows in O(nm) time or less [pdf]
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 [ECCC]
Siu On Chan (UC Berkeley)

Average-Case Lower Bounds for Formula Size [ECCC]
Ilan Komargodski (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

New Independent Source Extractors with Exponential Improvement [ECCC]
Xin Li (University of Washington)

Random Lattice Triangulations: Structure and Algorithms [arXiv]
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 [arXiv]
Xi Chen (Columbia University), Dimitris Paparas (Columbia University), and Mihalis Yannakakis (Columbia University)

Optimal Euclidean spanners: really short, thin and lanky [arXiv]
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 [arXiv]
Xiangrui Meng (Stanford University) and Michael W. Mahoney (Stanford University)

Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data [ePrint]
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 [arXiv]
Jelani Nelson (Institute for Advanced Study) and Huy L. Nguyen (Princeton University)

Approximating k-Median via Pseudo-Approximation [arXiv]
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 [arXiv]
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 [arXiv]
Jonathan Ullman (Harvard University)

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond [ePrint]
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 [arXiv]
Abhishek Bhowmick (University of Texas at Austin), Zeev Dvir (Princeton University), and Shachar Lovett (UC San Diego)

The complexity of finite-valued CSPs [arXiv]
Johan Thapper (Universite Paris-Sud 11) and Stanislav Zivny (University of Warwick)

Structured Recursive Separator Decompositions for Planar Graphs in Linear Time [arXiv]
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 [ECCC]
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 [pdf]
David G. Harris (University of Maryland) and Aravind Srinivasan (University of Maryland)

Low Rank Approximation and Regression in Input Sparsity Time [arXiv]
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 [arXiv]
Ofer Neiman (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems [HTML]
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 [arXiv]
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 [arXiv]
Andris Ambainis (University of Latvia)

Efficient rounding for the noncommutative Grothendieck inequality [arXiv]
Assaf Naor (New York University), Oded Regev (New York University), and Thomas Vidick (MIT)

A node-capacitated Okamura-Seymour theorem [arXiv]
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 [arXiv]
Alistair Sinclair (UC Berkeley) and Piyush Srivastava (UC Berkeley)

Beyond Worst-Case Analysis in Private Singular Vector Computation [arXiv]
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 [arXiv]
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 [arXiv]
Christoph Lenzen (Weizmann Institute of Science) and Boaz Patt-Shamir (Tel Aviv University)

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas [arXiv]
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 [arXiv]
Peter Burgisser (University of Paderborn) and Christian Ikenmeyer (University of Paderborn)

Shielding circuits with groups [ePrint]
Eric Miles (Northeastern University) and Emanuele Viola (Northeastern University)

Extending continuous maps: polynomiality and undecidability [pdf]
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 [arXiv]
Amin Coja-Oghlan (Goethe University) and Konstantinos Panagiotou (University of Munich)

Composable and Efficient Mechanisms [arXiv]
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 [arXiv]
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 [ECCC]
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 [arXiv]
Justin Hsu (University of Pennsylvania), Aaron Roth (University of Pennsylvania), and Jonathan Ullman (Harvard University)

Succinct Sampling from Discrete Distributions [pdf]
Karl Bringmann (Max Planck Institute for Informatics) and Kasper Green Larsen (MADALGO, Aarhus University)

The Orbit Problem in Higher Dimensions [pdf]
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 [ECCC]
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 [arXiv]
Daniel Kane (Stanford University) and Raghu Meka (Institute for Advanced Study and DIMACS)

Analysis of Spectral Partitioning through Higher Order Spectral Gap [arXiv]
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 [arXiv]
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

Stochastic Combinatorial Optimization via Poisson Approximation [arXiv]
Jian Li (IIIS, Tsinghua University) and Wen Yuan (IIIS, Tsinghua University)

Natural Proofs, Derandomization, and Lower Bounds [arXiv]
Ryan Williams (Stanford University)

Majority is Stablest : Discrete and SoS [arXiv]
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 [arXiv]
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 [arXiv]
Aleksandar Nikolov (Rutgers University), Kunal Talwar (Microsoft Research, Silicon Valley), and Li Zhang (Microsoft Research, Silicon Valley)

Fully device-independent quantum key distribution [arXiv]
Umesh Vazirani (UC Berkeley) and Thomas Vidick (MIT)

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 [ECCC]
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? [arXiv]
Moritz Hardt (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

The Approximate Rank of a Matrix and its Algorithmic Applications [ECCC]
Noga Alon (Tel Aviv University) and Santosh Vempala (Georgia Tech)

Communication Lower Bounds Using Directional Derivatives [ECCC]
Alexander A. Sherstov (UC Los Angelos)

Fast approximation algorithms for the diameter and radius of sparse graphs [pdf]
Liam Roditty (Bar Ilan University) and Virginia Vassilevska Williams (UC Berkeley and Stanford University)

Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs
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 [ePrint]
Omer Paneth (Boston University) and Nir Bitansky (Tel Aviv 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 [arXiv]
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 [arXiv]
Jonathan A. Kelner (MIT), Lorenzo Orecchia (MIT), Aaron Sidford (MIT), and Zeyuan Allen Zhu (MIT)

Low-rank Matrix Completion using Alternating Minimization [arXiv]
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 [arXiv]
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 [ECCC]
Mark Braverman (Princeton University), Ankit Garg (Princeton Unviersity), Denis Pankratov (University of Chicago), and Omri Weinstein (Princeton University)

Interactive Channel Capacity [ECCC]
Gillat Kol (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

Fast Hamiltonicity checking via bases of perfect matchings [arXiv]
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 [ePrint]
Kai-Min Chung (Cornell University), Rafael Pass (Cornell University), and Karn Seth (Cornell University)

A New Approach to Computing Maximum Flows using Electrical Flows
Satish Rao (UC Berkeley) and Nikhil Srivastava (Microsoft Research, India)

————————————————————————————-