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

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

- A Polynomial Time Algorithm for Lossy Population Recovery, by Ankur Moitra and Michael Saks [
**arXiv**]

- Direct products in communication complexity, by Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff [
**ECCC**]

- Arithmetic circuits: A chasm at depth three, by Ankit Gupta, Pritish Kamath, Neeraj Kayal and Ramprasad Saptharishi [
**ECCC**]

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

- The Parity of Directed Hamiltonian Cycles, by Andreas Björklund and Thore Husfeldt [
**arXiv**]

- Approximating Minimization Diagrams and Generalized Proximity Search, by Sariel Har-Peled and Nirman Kumar [
**arXiv**]

- Quantum 3-SAT is QMA
_{1}-complete, by David Gosset and Daniel Nagaj [**arXiv**]

- 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 [
**ECCC**]

- 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 [
**arXiv**]

- Common information and unique disjointness, by Gábor Braun, and Sebastian Pokutta [
**ECCC**]

- Chasing the k-colorability threshold, by Amin Coja-Oghlan and Dan Vilenchik [
**arXiv**]

- Three-player entangled XOR games are NP-hard to approximate, by Thomas Vidick [
**arXiv**]

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

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

- Approximation algorithms for Euler genus and related problems, by Chandra Chekuri and Anastasios Sidiropoulos [
**arXiv**]

- Polar Codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia [
**arXiv**]

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

- 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 [
**pdf**] [**video**]

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

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

- 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 [
**arXiv**]

- 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 [
**ePrint**]

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

- Strong Backdoors to Bounded Treewidth SAT, by Serge Gaspers and Stefan Szeider [
**arXiv**]

- Explicit Subspace Designs, by Venkatesan Guruswami and Swastik Kopparty [
**ECCC**]

- 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 [
**arXiv**]

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

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

- 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 [
**arXiv**]

- 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 [
**arXiv**]

- 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 [
**arXiv**]

- 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 [
**arXiv**]

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

- The Simple Economics of Approximately Optimal Auctions, Saeed Alaei, Hu Fu, Nima Haghpanah and Jason Hartline [
**arXiv**]

- Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford [
**arXiv**]

- Nearly Maximum Flows in Nearly Linear Time, by Jonah Sherman [
**arXiv**]

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

- 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 [
**arXiv**]

- Bandits with Knapsacks, Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins [
**arXiv**]

- 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à [
**arXiv**]

- A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, by Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider [
**arXiv**]

- The Complexity of Approximating Vertex Expansion, by Anand Louis, Prasad Raghavendra and Santosh Vempala [
**arXiv**]

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

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

- 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 [
**arXiv**]

- 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 [
**arXiv**]

- Local Privacy and Statistical Minimax Rates, by John C. Duchi, Michael I. Jordan, and Martin J. Wainwright [
**arXiv**]

- 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 [
**arXiv**]

- Understanding Incentives: Mechanism Design becomes Algorithm Design, by Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg [
**arXiv**]

- 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

———————————————————————————————————————————————————–