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 QMA1-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
———————————————————————————————————————————————————–
My Brain is Open 