FOCS 2013 – Accepted Papers

While there is a long tail of tasks ahead of us, the FOCS 2013 PC have completed its main task – selecting the program. The list of accepted papers is appended to this post, and I think it is a great collection of papers! We have unfortunately rejected many good papers, either because the presentation was not ready yet, or because we were over critical or simply because we made a mistake. Hopefully, the STOC 2014 PC will pick up our slack. Nevertheless, I am extremely pleased with our process. The PC invested a lot of effort into the electronic discussion, which made the selection less arbitrary and allowed us to have an incredibly constructive PC meeting. I may write some more in a couple of weeks (and will definitely open the blog for questions), but for now I’m going to do something I haven’t done in years and get completely off the grid for a week of recuperation.

FOCS 2013, Accepted Papers

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, by Jelani Nelson and Huy L. Nguyen

A Polynomial Time Algorithm for Lossy Population Recovery, Ankur Moitra and Michael Saks

Direct products in communication complexity, by Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff

Arithmetic circuits: A chasm at depth three, by Ankit Gupta, Pritish Kamath, Neeraj Kayal and Ramprasad Saptharishi

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs, by Joseph Cheriyan and Laszlo A. Vegh

The Parity of Directed Hamiltonian Cycles, by Andreas Björklund and Thore Husfeldt

Approximating Minimization Diagrams and Generalized Proximity Search, by Sariel Har-Peled and Nirman Kumar

Quantum 3-SAT is QMA₁-complete, by David Gosset and Daniel Nagaj

The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, by Vittorio Bilò, Michele Flammini and Luca Moscardelli

Strong LTCs with inverse poly-log rate and constant soundness, by Michael Viderman

All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, by Ken-ichi Kawarabayashi and Yusuke Kobayashi

Approximating Bin Packing within O(log OPT * log log OPT) bins, by Thomas Rothvoss

Common information and unique disjointness, by Gábor Braun, and Sebastian Pokutta

Chasing the k-colorability threshold, by Amin Coja-Oghlan and Dan Vilenchik

Three-player entangled XOR games are NP-hard to approximate, by Thomas Vidick

Fully Dynamic $(1+\epsilon)$-Approximate Matchings, by Manoj Gupta, and Richard Peng

Estimating the distance from testable affine-invariant properties, by Hamed Hatami and Shachar Lovett

Approximation algorithms for Euler genus and related problems, by Chandra Chekuri and Anastasios Sidiropoulos

Polar Codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia

An Optimal Randomized Online Algorithm for Reordering Buffer Management, by Noa Avigdor-Elgrabli and Yuval Rabani

Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Anna Adamaszek and Andreas Wiese

Playing Non-linear Games with Linear Oracles, by Dan Garber, and Elad Hazan

Faster Canonical Forms for Strongly Regular Graphs, by Laszlo Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes

Constant rate PCPs for circuit-SAT with sublinear query complexity, by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir and Henning Stichtenoth

How to Approximate A Set Without Knowing Its Size In Advance, by Rasmus Pagh, Gil Segev and Udi Wieder

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs, by Michael A. Forbes, and Amir Shpilka

On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions, by Natan Rubin

Element Distinctness, Frequency Moments, and Sliding Windows, by Paul Beame, Raphael Clifford and Widad Machmouchi

Spatial mixing and approximation algorithms for graphs with bounded connective constant, by Alistair Sinclair, Piyush Srivastava and Yitong Yin

Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors, by Harold N. Gabow and Piotr Sankowski

A linear time approximation scheme for Euclidean TSP, by Yair Bartal and Lee-Ad Gottlieb

Interactive Coding, Revisited, by Kai-Min Chung, Rafael Pass and Sidharth Telang

Improved approximation for 3-dimensional matching via bounded pathwidth local search, by Marek Cygan

Strong Backdoors to Bounded Treewidth SAT, by Serge Gaspers and Stefan Szeider

Explicit Subspace Designs, by Venkatesan Guruswami and Swastik Kopparty

Dynamic Approximate All-Pairs Shortest Paths: Breaking the $ \tilde O(mn) $ Barrier and Derandomization, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai

On Randomized Memoryless Algorithms for the Weighted $k$-server Problem, by Ashish Chiplunkar and Sundar Vishwanathan

Constant-Round Concurrent Zero Knowledge From P-Certificates, by Kai-Min Chung, Huijia Lin and Rafael Pass

Learning Sums of Independent Integer Random Variables, by Constantinos Daskalakis, Ilias Diakonikolas, Ryan O’Donnell, Rocco A. Servedio and Li-Yang Tan

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, by Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai

Online Node-weighted Steiner Forest and Extensions via Disk Paintings, by Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi

Klee’s Measure Problem Made Easy, by Timothy M. Chan

Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy, by Xin Li

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, by Aleksander Madry

Fourier sparsity, spectral norm, and the Log-rank conjecture, Hing Yin Tsang, Chung Hoi Wong, Ning Xie and Shengyu Zhang

Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring, by Vida Dujmović, Pat Morin, and David R. Wood

Average Case Lower Bounds for Monotone Switching Networks, by Yuval Filmus, Toniann Pitassi, Robert Robere and Stephen A. Cook

PCPs via low-degree long code and hardness for constrained hypergraph coloring, by Irit Dinur and Venkatesan Guruswami

The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable, by Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michał Pilipczuk

On the communication complexity of sparse set disjointness and exists-equal problems, Mert Sağlam and Gábor Tardos

The Simple Economics of Approximately Optimal Auctions, Saeed Alaei, Hu Fu, Nima Haghpanah and Jason Hartline

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford

Nearly Maximum Flows in Nearly Linear Time, by Jonah Sherman

Improved Average-Case Lower Bounds for DeMorgan Formula Size, by Ilan Komargodski, Ran Raz and Avishay Tal

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, by Vitaly Feldman and Jan Vondrak

Towards a better approximation for Sparsest Cut?, by Sanjeev Arora, Rong Ge and Ali Kemal Sinop

Bandits with Knapsacks, Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins

Approximate Constraint Satisfaction Requires Large LP Relaxations, by Siu On Chan, James R. Lee, Prasad Raghavendra and David Steurer

Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence, by Mikkel Thorup

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree, by Jochen Koenemann, Sina Sadeghian and Laura Sanità

A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, by Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider

The Complexity of Approximating Vertex Expansion, by Anand Louis, Prasad Raghavendra and Santosh Vempala

Tight Bounds for Set Disjointness in the Message Passing Model, by Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, Adam Marcus, Daniel A. Spielman and Nikhil Srivastava

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters

Iterative Row Sampling, by Mu Li, Gary L. Miller, and Richard Peng

Simultaneous Resettability from One-Way Functions, Kai-Min Chung, Rafail Ostrovsky, Rafael Pass and Ivan Visconti

Rational Protocol Design: Cryptography Against Incentive-driven Adversaries, by Juan Garay , Jonathan Katz, Ueli Maurer, Bjoern Tackmann and Vassilis Zikas

Non-positive curvature and the planar embedding conjecture, by Anastasios Sidiropoulos

Local Privacy and Statistical Minimax Rates, by John C. Duchi, Michael I. Jordan, and Martin J. Wainwright

The Moser-Tardos Framework with Partial Resampling, by David G. Harris and Aravind Srinivasan

On Clustering Induced Voronoi Diagrams, Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu

A forward-backward single-source shortest paths algorithm, by David Wilson and Uri Zwick

An O(c^k) n 5-Approximation Algorithm for Treewidth, by Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk

Understanding Incentives: Mechanism Design becomes Algorithm Design, by Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg

Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers, by Andrew Drucker

From Unprovability to Environementally Friendly Protocols, by Ran Canetti, Huijia Lin and Rafael Pass,

Adaptive Seeding in Social Networks, by Lior Seeman and Yaron Singer

Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy, by Raef Bassily, Adam Groce, Jonathan Katz and Adam Smith