| 2014 | (Nearly) Sample-Optimal Sparse Fourier Transform. Piotr Indyk, Michael Kapralov, Eric Price |
| 2014 | A Constant Factor Approximation Algorithm for Fault-Tolerant MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha |
| 2014 | A Cubic Algorithm for Computing Gaussian Volume. Ben Cousins, Santosh S. Vempala |
| 2014 | A Mazing 2+ Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Andreas Wiese |
| 2014 | A Near-Optimal Planarization Algorithm. Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh |
| 2014 | A New Perspective on Vertex Connectivity. Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn |
| 2014 | A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio |
| 2014 | A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices. Anna Adamaszek, Andreas Wiese |
| 2014 | A Simple FPTAS for Counting Edge Covers. Chengyu Lin, Jingcheng Liu, Pinyan Lu |
| 2014 | A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension. Esther Ezra |
| 2014 | A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2014 | A constructive algorithm for the Lovász Local Lemma on permutations. David G. Harris, Aravind Srinivasan |
| 2014 | A subexponential parameterized algorithm for Subset TSP on planar graphs. Philip N. Klein, Dániel Marx |
| 2014 | An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford |
| 2014 | An Excluded Grid Theorem for Digraphs with Forbidden Minors. Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2014 | An Optimal Lower Bound for Distinct Elements in the Message Passing Model. David P. Woodruff, Qin Zhang |
| 2014 | Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems. Samir Khuller, Manish Purohit, Kanthi K. Sarpatwar |
| 2014 | Annotations for Sparse Data Streams. Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler |
| 2014 | Approximating David Eisenstat, Philip N. Klein, Claire Mathieu |
| 2014 | Approximating Local Homology from Samples. Primoz Skraba, Bei Wang |
| 2014 | Approximating Minimum Cost Connectivity Orientation and Augmentation. Mohit Singh, László A. Végh |
| 2014 | Approximating matching size from random streams. Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2014 | Approximation Algorithm for Sparsest Anand Louis, Konstantin Makarychev |
| 2014 | Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover. Amol Deshpande, Lisa Hellerstein, Devorah Kletenik |
| 2014 | Approximation-Tolerant Model-Based Compressive Sensing. Chinmay Hegde, Piotr Indyk, Ludwig Schmidt |
| 2014 | Arboricity and spanning-tree packing in random graphs with an application to load balancing. Pu Gao, Xavier Pérez-Giménez, Cristiane M. Sato |
| 2014 | Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li |
| 2014 | Better Approximation Algorithms for the Graph Diameter. Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams |
| 2014 | Better Approximation Bounds for the Joint Replenishment Problem. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall |
| 2014 | Beyond Locality-Sensitive Hashing. Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn |
| 2014 | Bicriteria data compression. Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, Rossano Venturini |
| 2014 | Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan |
| 2014 | Broadcast Throughput in Radio Networks: Routing vs. Network Coding. Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian |
| 2014 | Cache-Adaptive Algorithms. Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, Samuel McCauley |
| 2014 | Causal Erasure Channels. Raef Bassily, Adam D. Smith |
| 2014 | Clustering and Mixing Times for Segregation Models on ℤ Prateek Bhakta, Sarah Miracle, Dana Randall |
| 2014 | Competitive Analysis via Regularization. Niv Buchbinder, Shahar Chen, Joseph Naor |
| 2014 | Computing Cut-Based Hierarchical Decompositions in Almost Linear Time. Harald Räcke, Chintan Shah, Hanjo Täubig |
| 2014 | Concurrent Range Reporting in Two-Dimensional Space. Peyman Afshani, Cheng Sheng, Yufei Tao, Bryan T. Wilkinson |
| 2014 | Constrained Signaling in Auction Design. Shaddin Dughmi, Nicole Immorlica, Aaron Roth |
| 2014 | Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time. Andreas Björklund, Petteri Kaski, Lukasz Kowalik |
| 2014 | Cutting corners cheaply, or how to remove Steiner points. Lior Kamma, Robert Krauthgamer, Huy L. Nguyen |
| 2014 | Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles. Thomas Dueholm Hansen, Haim Kaplan, Uri Zwick |
| 2014 | Disjoint Set Union with Randomized Linking. Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan |
| 2014 | Dynamic Task Allocation in Asynchronous Shared Memory. Dan Alistarh, James Aspnes, Michael A. Bender, Rati Gelashvili, Seth Gilbert |
| 2014 | Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh |
| 2014 | Efficient quantum protocols for XOR functions. Shengyu Zhang |
| 2014 | Exploiting Metric Structure for Efficient Private Query Release. Zhiyi Huang, Aaron Roth |
| 2014 | Fast Computation of Output-Sensitive Maxima in a Word RAM. Peyman Afshani |
| 2014 | Fast algorithms for maximizing submodular functions. Ashwinkumar Badanidiyuru, Jan Vondrák |
| 2014 | Faster Agreement via a Spectral Method for Detecting Malicious Behavior. Valerie King, Jared Saia |
| 2014 | Fault Tolerant Approximate BFS Structures. Merav Parter, David Peleg |
| 2014 | Finding orthogonal vectors in discrete structures. Ryan Williams, Huacheng Yu |
| 2014 | Finding small patterns in permutations in linear time. Sylvain Guillemot, Dániel Marx |
| 2014 | First Come First Served for Online Slot Allocation and Huffman Coding. Monik Khare, Claire Mathieu, Neal E. Young |
| 2014 | Flow-Based Algorithms for Local Graph Clustering. Lorenzo Orecchia, Zeyuan Allen Zhu |
| 2014 | Four Soviets Walk the Dog - with an Application to Alt's Conjecture. Kevin Buchin, Maike Buchin, Wouter Meulemans, Wolfgang Mulzer |
| 2014 | Half-integrality, LP-branching and FPT Algorithms. Magnus Wahlström |
| 2014 | Hallucination Helps: Energy Efficient Virtual Circuit Routing. Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein |
| 2014 | Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. Subhash Khot, Rishi Saket |
| 2014 | Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou |
| 2014 | Hereditary properties of permutations are strongly testable. Tereza Klimosová, Daniel Král' |
| 2014 | Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou |
| 2014 | Implicit Manifold Reconstruction. Siu-Wing Cheng, Man-Kwun Chiu |
| 2014 | Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs. Wang Chi Cheung, Michel X. Goemans, Sam Chiu-wai Wong |
| 2014 | Improved Approximation Algorithm for Two-Dimensional Bin Packing. Nikhil Bansal, Arindam Khan |
| 2014 | Improved Concentration Bounds for Count-Sketch. Gregory T. Minton, Eric Price |
| 2014 | Improved bounds and algorithms for graph cuts and network reliability. David G. Harris, Aravind Srinivasan |
| 2014 | Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. Thomas Dueholm Hansen, Mike Paterson, Uri Zwick |
| 2014 | Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract. Will Ma |
| 2014 | Independent Set in Daniel Lokshtanov, Martin Vatshelle, Yngve Villanger |
| 2014 | Influence Maximization in Undirected Networks. Sanjeev Khanna, Brendan Lucier |
| 2014 | Integer quadratic programming in the plane. Alberto Del Pia, Robert Weismantel |
| 2014 | Interval Deletion is Fixed-Parameter Tractable. Yixin Cao, Dániel Marx |
| 2014 | Intrinsic universality in tile self-assembly requires cooperation. Pierre-Etienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods |
| 2014 | Large induced subgraphs via triangulations and CMSO. Fedor V. Fomin, Ioan Todinca, Yngve Villanger |
| 2014 | Learning Entangled Single-Sample Gaussians. Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi |
| 2014 | Learning Sparse Polynomial Functions. Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang |
| 2014 | Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts. M. S. Ramanujan, Saket Saurabh |
| 2014 | Linear-Time FPT Algorithms via Network Flow. Yoichi Iwata, Keigo Oka, Yuichi Yoshida |
| 2014 | MCMC sampling colourings and independent sets of Charilaos Efthymiou |
| 2014 | Maintaining Assignments Online: Matching, Scheduling, and Flows. Anupam Gupta, Amit Kumar, Cliff Stein |
| 2014 | Making Octants Colorful and Related Covering Decomposition Problems. Jean Cardinal, Kolja B. Knauer, Piotr Micek, Torsten Ueckerdt |
| 2014 | Maximizing Bisubmodular and Justin Ward, Stanislav Zivný |
| 2014 | Maximizing Social Influence in Nearly Optimal Time. Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Brendan Lucier |
| 2014 | Minimum Anupam Gupta, Anastasios Sidiropoulos |
| 2014 | Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable. Laurent Bulteau, Christian Komusiewicz |
| 2014 | Model-based Sketching and Recovery with Expanders. Bubacarr Bah, Luca Baldassarre, Volkan Cevher |
| 2014 | Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs. Kook Jin Ahn, Sudipto Guha |
| 2014 | Near-optimal labeling schemes for nearest common ancestors. Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen |
| 2014 | New Approximations for Reordering Buffer Management. Sungjin Im, Benjamin Moseley |
| 2014 | New constructions of RIP matrices with fast multiplication and fewer rows. Jelani Nelson, Eric Price, Mary Wootters |
| 2014 | Non-Uniform Graph Partitioning. Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar |
| 2014 | On Computability of Equilibria in Markets with Production. Jugal Garg, Vijay V. Vazirani |
| 2014 | On Sketching Matrix Norms and the Top Singular Vector. Yi Li, Huy L. Nguyen, David P. Woodruff |
| 2014 | On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank. Herbert Edelsbrunner, Salman Parsa |
| 2014 | On the Lattice Isomorphism Problem. Ishay Haviv, Oded Regev |
| 2014 | On the compatibility of quartet trees. Noga Alon, Sagi Snir, Raphael Yuster |
| 2014 | On the optimality of approximation schemes for the classical scheduling problem. Lin Chen, Klaus Jansen, Guochuan Zhang |
| 2014 | Online Steiner Tree with Deletions. Anupam Gupta, Amit Kumar |
| 2014 | Optimal Algorithms for Testing Closeness of Discrete Distributions. Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant |
| 2014 | Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges. Peyman Afshani, Konstantinos Tsakalidis |
| 2014 | Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Venkatesan Guruswami, Chaoping Xing |
| 2014 | Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence. Georgios Piliouras, Jeff S. Shamma |
| 2014 | Packing Yutaro Yamaguchi |
| 2014 | Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems. Bundit Laekhanukit |
| 2014 | Partitioning into Expanders. Shayan Oveis Gharan, Luca Trevisan |
| 2014 | Pipage Rounding, Pessimistic Estimators and Matrix Concentration. Nicholas J. A. Harvey, Neil Olver |
| 2014 | Point Line Cover: The Easy Kernel is Essentially Tight. Stefan Kratsch, Geevarghese Philip, Saurabh Ray |
| 2014 | Polynomial Solvability of Variants of the Trust-Region Subproblem. Daniel Bienstock, Alexander Michalka |
| 2014 | Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. René Sitters |
| 2014 | Polynomiality for Bin Packing with a Constant Number of Item Types. Michel X. Goemans, Thomas Rothvoß |
| 2014 | Positivity Problems for Low-Order Linear Recurrence Sequences. Joël Ouaknine, James Worrell |
| 2014 | Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms. Nikhil R. Devanur, Zhiyi Huang |
| 2014 | Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 Chandra Chekuri |
| 2014 | Prophet Inequalities with Limited Information. Pablo Daniel Azar, Robert Kleinberg, S. Matthew Weinberg |
| 2014 | Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints. T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao |
| 2014 | Relative Errors for Deterministic Low-Rank Matrix Approximations. Mina Ghashami, Jeff M. Phillips |
| 2014 | Robust Satisfiability of Systems of Equations. Peter Franek, Marek Krcál |
| 2014 | Selection and Sorting in the "Restore" Model. Timothy M. Chan, J. Ian Munro, Venkatesh Raman |
| 2014 | Smoothed Analysis of Local Search for the Maximum-Cut Problem. Michael Etscheid, Heiko Röglin |
| 2014 | Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball. Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller, Amir Nayyeri, Richard Peng, Noel Walkington |
| 2014 | Space complexity of list László Egri, Pavol Hell, Benoît Larose, Arash Rafiey |
| 2014 | Streaming Balanced Graph Partitioning Algorithms for Random Graphs. Isabelle Stanton |
| 2014 | Submodular Maximization with Cardinality Constraints. Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz |
| 2014 | Testing Surface Area. Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu |
| 2014 | Testing equivalence between distributions using conditional samples. Clément L. Canonne, Dana Ron, Rocco A. Servedio |
| 2014 | The Complexity of Optimal Mechanism Design. Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos |
| 2014 | The Complexity of Optimal Multidimensional Pricing. Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
| 2014 | The Complexity of Order Type Isomorphism. Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, Stefanie Wuhrer |
| 2014 | The Generalized Terminal Backup Problem. Attila Bernáth, Yusuke Kobayashi |
| 2014 | Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx |
| 2014 | Tight Bounds for Rumor Spreading with Vertex Expansion. George Giakkoupis |
| 2014 | Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids. Martin Dietzfelbinger, Philipp Woelfel |
| 2014 | Timing in chemical reaction networks. David Doty |
| 2014 | Towards (1 + Alexandr Andoni, Anupam Gupta, Robert Krauthgamer |
| 2014 | Uniform random sampling of simple branched coverings of the sphere by itself. Enrica Duchi, Dominique Poulalhon, Gilles Schaeffer |