| 2013 | 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October, 26-29, 2013 |
| 2013 | A Forward-Backward Single-Source Shortest Paths Algorithm. David B. Wilson, Uri Zwick |
| 2013 | A Linear Time Approximation Scheme for Euclidean TSP. Yair Bartal, Lee-Ad Gottlieb |
| 2013 | A Polynomial Time Algorithm for Lossy Population Recovery. Ankur Moitra, Michael E. Saks |
| 2013 | A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider |
| 2013 | A Tight Bound for Set Disjointness in the Message-Passing Model. Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan |
| 2013 | Adaptive Seeding in Social Networks. Lior Seeman, Yaron Singer |
| 2013 | Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors. Harold N. Gabow, Piotr Sankowski |
| 2013 | All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs. Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2013 | An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree. Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità |
| 2013 | An O(c^k n) 5-Approximation Algorithm for Treewidth. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk |
| 2013 | An optimal randomized online algorithm for reordering buffer management. Noa Avigdor-Elgrabli, Yuval Rabani |
| 2013 | Approximate Constraint Satisfaction Requires Large LP Relaxations. Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer |
| 2013 | Approximating Bin Packing within O(log OPT * Log Log OPT) Bins. Thomas Rothvoß |
| 2013 | Approximating Minimization Diagrams and Generalized Proximity Search. Sariel Har-Peled, Nirman Kumar |
| 2013 | Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. Joseph Cheriyan, László A. Végh |
| 2013 | Approximation Algorithms for Euler Genus and Related Problems. Chandra Chekuri, Anastasios Sidiropoulos |
| 2013 | Approximation Schemes for Maximum Weight Independent Set of Rectangles. Anna Adamaszek, Andreas Wiese |
| 2013 | Arithmetic Circuits: A Chasm at Depth Three. Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi |
| 2013 | Average Case Lower Bounds for Monotone Switching Networks. Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook |
| 2013 | Bandits with Knapsacks. Ashwinkumar Badanidiyuru, Robert Kleinberg, Aleksandrs Slivkins |
| 2013 | Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters |
| 2013 | Chasing the K-Colorability Threshold. Amin Coja-Oghlan, Dan Vilenchik |
| 2013 | Common Information and Unique Disjointness. Gábor Braun, Sebastian Pokutta |
| 2013 | Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth |
| 2013 | Constant-Round Concurrent Zero Knowledge from P-Certificates. Kai-Min Chung, Huijia Lin, Rafael Pass |
| 2013 | Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy. Raef Bassily, Adam Groce, Jonathan Katz, Adam D. Smith |
| 2013 | Direct Products in Communication Complexity. Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff |
| 2013 | Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2013 | Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems. Yin Tat Lee, Aaron Sidford |
| 2013 | Element Distinctness, Frequency Moments, and Sliding Windows. Paul Beame, Raphaël Clifford, Widad Machmouchi |
| 2013 | Estimating the Distance from Testable Affine-Invariant Properties. Hamed Hatami, Shachar Lovett |
| 2013 | Explicit Subspace Designs. Venkatesan Guruswami, Swastik Kopparty |
| 2013 | Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. Xin Li |
| 2013 | Faster Canonical Forms for Strongly Regular Graphs. László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes |
| 2013 | Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang |
| 2013 | From Unprovability to Environmentally Friendly Protocols. Ran Canetti, Huijia Lin, Rafael Pass |
| 2013 | Fully Dynamic (1+ e)-Approximate Matchings. Manoj Gupta, Richard Peng |
| 2013 | How to Approximate a Set without Knowing Its Size in Advance. Rasmus Pagh, Gil Segev, Udi Wieder |
| 2013 | Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. Marek Cygan |
| 2013 | Improved Average-Case Lower Bounds for DeMorgan Formula Size. Ilan Komargodski, Ran Raz, Avishay Tal |
| 2013 | Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses. Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai |
| 2013 | Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. Adam Marcus, Daniel A. Spielman, Nikhil Srivastava |
| 2013 | Iterative Row Sampling. Mu Li, Gary L. Miller, Richard Peng |
| 2013 | Klee's Measure Problem Made Easy. Timothy M. Chan |
| 2013 | Knowledge-Preserving Interactive Coding. Kai-Min Chung, Rafael Pass, Sidharth Telang |
| 2013 | Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring. Vida Dujmovic, Pat Morin, David R. Wood |
| 2013 | Learning Sums of Independent Integer Random Variables. Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2013 | Local Privacy and Statistical Minimax Rates. John C. Duchi, Michael I. Jordan, Martin J. Wainwright |
| 2013 | Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back. Aleksander Madry |
| 2013 | Nearly Maximum Flows in Nearly Linear Time. Jonah Sherman |
| 2013 | Non-positive Curvature and the Planar Embedding Conjecture. Anastasios Sidiropoulos |
| 2013 | Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers. Andrew Drucker |
| 2013 | OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings. Jelani Nelson, Huy L. Nguyen |
| 2013 | On Clustering Induced Voronoi Diagrams. Danny Z. Chen, Ziyun Huang, Yangwei Liu, Jinhui Xu |
| 2013 | On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions. Natan Rubin |
| 2013 | On Randomized Memoryless Algorithms for the Weighted K-Server Problem. Ashish Chiplunkar, Sundar Vishwanathan |
| 2013 | On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. Mert Saglam, Gábor Tardos |
| 2013 | Online Node-Weighted Steiner Forest and Extensions via Disk Paintings. Mohammad Taghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi |
| 2013 | Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. Vitaly Feldman, Jan Vondrák |
| 2013 | PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. Irit Dinur, Venkatesan Guruswami |
| 2013 | Playing Non-linear Games with Linear Oracles. Dan Garber, Elad Hazan |
| 2013 | Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. Venkatesan Guruswami, Patrick Xia |
| 2013 | Quantum 3-SAT Is QMA1-Complete. David Gosset, Daniel Nagaj |
| 2013 | Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. Michael A. Forbes, Amir Shpilka |
| 2013 | Rational Protocol Design: Cryptography against Incentive-Driven Adversaries. Juan A. Garay, Jonathan Katz, Ueli Maurer, Björn Tackmann, Vassilis Zikas |
| 2013 | Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence. Mikkel Thorup |
| 2013 | Simultaneous Resettability from One-Way Functions. Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Ivan Visconti |
| 2013 | Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant. Alistair Sinclair, Piyush Srivastava, Yitong Yin |
| 2013 | Strong Backdoors to Bounded Treewidth SAT. Serge Gaspers, Stefan Szeider |
| 2013 | Strong LTCs with Inverse Poly-Log Rate and Constant Soundness. Michael Viderman |
| 2013 | The Complexity of Approximating Vertex Expansion. Anand Louis, Prasad Raghavendra, Santosh S. Vempala |
| 2013 | The Moser-Tardos Framework with Partial Resampling. David G. Harris, Aravind Srinivasan |
| 2013 | The Parity of Directed Hamiltonian Cycles. Andreas Björklund, Thore Husfeldt |
| 2013 | The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk |
| 2013 | The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant. Vittorio Bilò, Michele Flammini, Luca Moscardelli |
| 2013 | The Simple Economics of Approximately Optimal Auctions. Saeed Alaei, Hu Fu, Nima Haghpanah, Jason D. Hartline |
| 2013 | Three-Player Entangled XOR Games Are NP-Hard to Approximate. |
| 2013 | Towards a Better Approximation for Sparsest Cut? Sanjeev Arora, Rong Ge, Ali Kemal Sinop |
| 2013 | Understanding Incentives: Mechanism Design Becomes Algorithm Design. Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg |