| 2014 | (2 + epsilon)-Sat Is NP-Hard. Per Austrin, Johan Håstad, Venkatesan Guruswami |
| 2014 | 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014 |
| 2014 | A Counter-example to Karlin's Strong Conjecture for Fictitious Play. Constantinos Daskalakis, Qinxuan Pan |
| 2014 | A Simple and Approximately Optimal Mechanism for an Additive Buyer. Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg |
| 2014 | Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions. Umang Bhaskar, Katrina Ligett, Leonard J. Schulman, Chaitanya Swamy |
| 2014 | An Algebraic Approach to Non-malleability. Vipul Goyal, Silas Richelson, Alon Rosen, Margarita Vald |
| 2014 | An Automatic Inequality Prover and Instance Optimal Identity Testing. Gregory Valiant, Paul Valiant |
| 2014 | An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan |
| 2014 | Barriers to Near-Optimal Equilibria. Tim Roughgarden |
| 2014 | Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. Itai Benjamini, Gil Cohen, Igor Shinkar |
| 2014 | Bounds on the Permanent and Some Applications. Leonid Gurvits, Alex Samorodnitsky |
| 2014 | Chasing Ghosts: Competing with Stateful Policies. Uriel Feige, Tomer Koren, Moshe Tennenholtz |
| 2014 | Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. Joshua A. Grochow, Toniann Pitassi |
| 2014 | Complexity Classification of Local Hamiltonian Problems. Toby S. Cubitt, Ashley Montanaro |
| 2014 | Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. Radu Curticapean, Dániel Marx |
| 2014 | Constructive Discrepancy Minimization for Convex Sets. Thomas Rothvoß |
| 2014 | Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2014 | Digital Morphogenesis via Schelling Segregation. George Barmpalias, Richard Elwes, Andy Lewis-Pye |
| 2014 | Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. Mihai Patrascu, Mikkel Thorup |
| 2014 | Exponential Separation of Information and Communication. Anat Ganor, Gillat Kol, Ran Raz |
| 2014 | Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2014 | Generating k-Independent Variables in Constant Time. Tobias Christiani, Rasmus Pagh |
| 2014 | Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors. Subhash Khot, Rishi Saket |
| 2014 | Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. François Le Gall |
| 2014 | Interactive Channel Capacity Revisited. Bernhard Haeupler |
| 2014 | LP-Based Algorithms for Capacitated Facility Location. Hyung-Chan An, Mohit Singh, Ola Svensson |
| 2014 | List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Mark Braverman, Klim Efremenko |
| 2014 | Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani |
| 2014 | Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets. Nima Anari, Gagan Goel, Afshin Nikzad |
| 2014 | Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen |
| 2014 | New Algorithms and Lower Bounds for Monotonicity Testing. Xi Chen, Rocco A. Servedio, Li-Yang Tan |
| 2014 | Noisy Interactive Quantum Communication. Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger |
| 2014 | Non-malleable Codes against Constant Split-State Tampering. Eshan Chattopadhyay, David Zuckerman |
| 2014 | Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes. Sian-Jheng Lin, Wei-Ho Chung, Yunghsiang S. Han |
| 2014 | O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. Oded Lachish |
| 2014 | On Learning and Testing Dynamic Environments. Oded Goldreich, Dana Ron |
| 2014 | On the AC0 Complexity of Subgraph Isomorphism. Yuan Li, Alexander A. Razborov, Benjamin Rossman |
| 2014 | On the Hardness of Signaling. Shaddin Dughmi |
| 2014 | On the Power of Homogeneous Depth 4 Arithmetic Circuits. Mrinal Kumar, Shubhangi Saraf |
| 2014 | One-Way Functions and (Im)Perfect Obfuscation. Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, Eylon Yogev |
| 2014 | Online Bipartite Matching in Offline Time. Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych |
| 2014 | Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. Mohsen Ghaffari, Bernhard Haeupler |
| 2014 | Outsourcing Private RAM Computation. Craig Gentry, Shai Halevi, Mariana Raykova, Daniel Wichs |
| 2014 | Parallel Repetition from Fortification. Dana Moshkovitz |
| 2014 | Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow. Yin Tat Lee, Aaron Sidford |
| 2014 | Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. Amir Abboud, Virginia Vassilevska Williams |
| 2014 | Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs. Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai |
| 2014 | Preventing False Discovery in Interactive Data Analysis Is Hard. Moritz Hardt, Jonathan R. Ullman |
| 2014 | Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. Raef Bassily, Adam D. Smith, Abhradeep Thakurta |
| 2014 | Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. Andris Ambainis, Ansis Rosmanis, Dominique Unruh |
| 2014 | Ramanujan Complexes and Bounded Degree Topological Expanders. Tali Kaufman, David Kazhdan, Alexander Lubotzky |
| 2014 | Random Walks That Find Perfect Objects and the Lovasz Local Lemma. Dimitris Achlioptas, Fotis Iliopoulos |
| 2014 | Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM. George Giakkoupis, Philipp Woelfel |
| 2014 | Sample-Optimal Fourier Sampling in Any Constant Dimension. Piotr Indyk, Michael Kapralov |
| 2014 | Satisfiability and Evolution. Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan |
| 2014 | SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, Kirk Pruhs |
| 2014 | Settling the APX-Hardness Status for Geometric Set Cover. Nabil H. Mustafa, Rajiv Raman, Saurabh Ray |
| 2014 | Shrinkage of De Morgan Formulae by Spectral Techniques. Avishay Tal |
| 2014 | Single Pass Spectral Sparsification in Dynamic Streams. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford |
| 2014 | Solving Optimization Problems with Diseconomies of Scale via Decoupling. Konstantin Makarychev, Maxim Sviridenko |
| 2014 | Spectral Approaches to Nearest Neighbor Search. Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer |
| 2014 | The Communication Complexity of Distributed epsilon-Approximations. Zengfeng Huang, Ke Yi |
| 2014 | The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. Jin-Yi Cai, Heng Guo, Tyson Williams |
| 2014 | The Dyck Language Edit Distance Problem in Near-Linear Time. Barna Saha |
| 2014 | Threesomes, Degenerates, and Love Triangles. Allan Grønlund Jørgensen, Seth Pettie |
| 2014 | Topology Matters in Communication. Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra |
| 2014 | Total Space in Resolution. Ilario Bonacina, Nicola Galesi, Neil Thapen |
| 2014 | Understanding Alternating Minimization for Matrix Completion. Moritz Hardt |
| 2014 | Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. Karl Bringmann |