| 2016 | A Fast Approximation for Maximum Weight Matroid Intersection. Chandra Chekuri, Kent Quanrud |
| 2016 | A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees. Sunil Arya, David M. Mount |
| 2016 | A Faster Subquadratic Algorithm for Finding Outlier Correlations. Matti Karppa, Petteri Kaski, Jukka Kohonen |
| 2016 | Algorithmic Complexity of Power Law Networks. Pawel Brach, Marek Cygan, Jakub Lacki, Piotr Sankowski |
| 2016 | Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution. David G. Harris, Aravind Srinivasan |
| 2016 | Algorithms and Adaptivity Gaps for Stochastic Probing. Anupam Gupta, Viswanath Nagarajan, Sahil Singla |
| 2016 | An Algorithmic Hypergraph Regularity Lemma. Brendan Nagle, Vojtech Rödl, Mathias Schacht |
| 2016 | An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles. Pankaj K. Agarwal, Kyle Fox, Oren Salzman |
| 2016 | An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra. Robert Hildebrand, Robert Weismantel, Kevin Zemmer |
| 2016 | An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem. Christos Kalaitzis |
| 2016 | An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. Ran Duan, Jugal Garg, Kurt Mehlhorn |
| 2016 | An Improved Distributed Algorithm for Maximal Independent Set. Mohsen Ghaffari |
| 2016 | An O(log Lin Chen, Nicole Megow, Kevin Schewior |
| 2016 | An improved bound on the fraction of correctable deletions. Boris Bukh, Venkatesan Guruswami |
| 2016 | Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff. Christian Wulff-Nilsen |
| 2016 | Approximate Undirected Maximum Flows in Richard Peng |
| 2016 | Approximately Efficient Double Auctions with Strong Budget Balance. Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta |
| 2016 | Approximating Low-Stretch Spanners. Michael Dinitz, Zeyu Zhang |
| 2016 | Approximating capacitated Shi Li |
| 2016 | Approximating the Sariel Har-Peled, Haim Kaplan, Micha Sharir |
| 2016 | Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. Amir Abboud, Virginia Vassilevska Williams, Joshua R. Wang |
| 2016 | Approximation of non-boolean 2CSP. Guy Kindler, Alexandra Kolla, Luca Trevisan |
| 2016 | Approximation schemes for machine scheduling with resource (in-)dependent processing times. Klaus Jansen, Marten Maack, Malin Rau |
| 2016 | Balanced Allocation: Patience is not a Virtue. John Augustine, William K. Moses Jr., Amanda Redlich, Eli Upfal |
| 2016 | Better Distance Preservers and Additive Spanners. Greg Bodwin, Virginia Vassilevska Williams |
| 2016 | Beyond the Richter-Thomassen Conjecture. János Pach, Natan Rubin, Gábor Tardos |
| 2016 | Blocking Optimal Attila Bernáth, Tamás Király |
| 2016 | Bounds for Random Constraint Satisfaction Problems via Spatial Coupling. Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke |
| 2016 | Canonical Paths for MCMC: from Art to Science. Lingxiao Huang, Pinyan Lu, Chihao Zhang |
| 2016 | Characterisation of Strongly Stable Matchings. Adam Kunysz, Katarzyna E. Paluch, Pratik Ghosal |
| 2016 | Clustering Problems on Sliding Windows. Vladimir Braverman, Harry Lang, Keith D. Levin, Morteza Monemizadeh |
| 2016 | Clustering time series under the Fréchet distance. Anne Driemel, Amer Krivosija, Christian Sohler |
| 2016 | Communication Complexity of Permutation-Invariant Functions. Badih Ghazi, Pritish Kamath, Madhu Sudan |
| 2016 | Communication with Contextual Uncertainty. Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan |
| 2016 | Computing in continuous space with self-assembling polygonal tiles (extended abstract). Oscar Gilbert, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
| 2016 | Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture. Guillaume Chapuy, Guillem Perarnau |
| 2016 | Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation. Chandra Chekuri, Vivek Madan |
| 2016 | Constructive algorithm for path-width of matroids. Jisu Jeong, Eun Jung Kim, Sang-il Oum |
| 2016 | Designing Networks with Good Equilibria under Uncertainty. George Christodoulou, Alkmini Sgouritsa |
| 2016 | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. Timothy M. Chan, Ryan Williams |
| 2016 | Deterministic Algorithms for Submodular Maximization Problems. Niv Buchbinder, Moran Feldman |
| 2016 | Directed multicut is Marcin Pilipczuk, Magnus Wahlström |
| 2016 | Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting. Robert Ganian, M. S. Ramanujan, Stefan Szeider |
| 2016 | Discrete Gaussian Sampling Reduces to CVP and SVP. Noah Stephens-Davidowitz |
| 2016 | Distance in the Forest Fire Model How far are you from Eve? Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu |
| 2016 | Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. Mohsen Ghaffari, Bernhard Haeupler |
| 2016 | Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach. David Peleg, Shay Solomon |
| 2016 | Dynamic DFS in Undirected Graphs: breaking the O( Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan |
| 2016 | Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky |
| 2016 | Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf |
| 2016 | Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. Jean-François Biasse, Fang Song |
| 2016 | Error Amplification for Pairwise Spanner Lower Bounds. Amir Abboud, Greg Bodwin |
| 2016 | Evolutionary Dynamics in Finite Populations Mix Rapidly. Ioannis Panageas, Piyush Srivastava, Nisheeth K. Vishnoi |
| 2016 | Exact and Approximation Algorithms for Weighted Matroid Intersection. Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama |
| 2016 | Expanders via Local Edge Flips. Zeyuan Allen Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab S. Mirrokni, Lorenzo Orecchia |
| 2016 | Faster Fully Dynamic Matchings with Small Approximation Ratios. Aaron Bernstein, Cliff Stein |
| 2016 | Finding Perfect Matchings in Bipartite Hypergraphs. Chidambaram Annamalai |
| 2016 | Finding a Stable Allocation in Polymatroid Intersection. Satoru Iwata, Yu Yokoi |
| 2016 | Focused Stochastic Local Search and the Lovász Local Lemma. Dimitris Achlioptas, Fotis Iliopoulos |
| 2016 | Front Matter. |
| 2016 | Gowers Norm, Function Limits, and Parameter Estimation. Yuichi Yoshida |
| 2016 | Higher Lower Bounds from the 3SUM Conjecture. Tsvi Kopelowitz, Seth Pettie, Ely Porat |
| 2016 | How to Round Subspaces: A New Spectral Clustering Algorithm. Ali Kemal Sinop |
| 2016 | How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Maxwell Young |
| 2016 | Improved Approximation Algorithms for Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida |
| 2016 | Improved Approximation for Vector Bin Packing. Nikhil Bansal, Marek Eliás, Arindam Khan |
| 2016 | Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee |
| 2016 | Improved Deterministic Algorithms for Linear Programming in Low Dimensions. Timothy M. Chan |
| 2016 | Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover. Amit Chakrabarti, Anthony Wirth |
| 2016 | Independence and Efficient Domination on Daniel Lokshtanov, Marcin Pilipczuk, Erik Jan van Leeuwen |
| 2016 | Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders. Xue Chen |
| 2016 | Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions. Mark Braverman, Jieming Mao, S. Matthew Weinberg |
| 2016 | Jointly Private Convex Programming. Justin Hsu, Zhiyi Huang, Aaron Roth, Zhiwei Steven Wu |
| 2016 | Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova |
| 2016 | Learning and Efficiency in Games with Dynamic Population. Thodoris Lykouris, Vasilis Syrgkanis, Éva Tardos |
| 2016 | Linear Recognition of Almost Interval Graphs. Yixin Cao |
| 2016 | Local-on-Average Distributed Tasks. Merav Parter, David Peleg, Shay Solomon |
| 2016 | Locality-sensitive Hashing without False Negatives. Rasmus Pagh |
| 2016 | Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer |
| 2016 | Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems. Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukás Mach, Michal Pilipczuk |
| 2016 | Make-to-Order Integrated Scheduling and Distribution. Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi |
| 2016 | Markovian Hitters and the Complexity of Blind Rendezvous. Sixia Chen, Matthew Dippel, Alexander Russell, Abhishek Samanta, Ravi Sundaram |
| 2016 | Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev |
| 2016 | Multiscale Mapper: Topological Summarization via Codomain Covers. Tamal K. Dey, Facundo Mémoli, Yusu Wang |
| 2016 | Natural Algorithms for Flow Problems. Damian Straszak, Nisheeth K. Vishnoi |
| 2016 | Near-Optimal Light Spanners. Shiri Chechik, Christian Wulff-Nilsen |
| 2016 | Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform. Mahdi Cheraghchi, Piotr Indyk |
| 2016 | Nearly Optimal NP-Hardness of Unique Coverage. Venkatesan Guruswami, Euiwoong Lee |
| 2016 | Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities. Michael B. Cohen |
| 2016 | Nearly-optimal bounds for sparse recovery in generic norms, with applications to Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff |
| 2016 | New Bounds for Approximating Extremal Distances in Undirected Graphs. Massimo Cairo, Roberto Grossi, Romeo Rizzi |
| 2016 | New directions in nearest neighbor searching with applications to lattice sieving. Anja Becker, Léo Ducas, Nicolas Gama, Thijs Laarhoven |
| 2016 | Non-convex Compressed Sensing with the Sum-of-Squares Method. Tasuku Soma, Yuichi Yoshida |
| 2016 | Obstructions for three-coloring graphs with one forbidden induced subgraph. Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong |
| 2016 | On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs. Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck |
| 2016 | On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion. Yair Bartal, Arnold Filtser, Ofer Neiman |
| 2016 | On approximating strip packing with a better ratio than 3/2. Giorgi Nadiradze, Andreas Wiese |
| 2016 | On the Complexity of Dynamic Mechanism Design. Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein |
| 2016 | On the Economic Efficiency of the Combinatorial Clock Auction. Nicolas Bousquet, Yang Cai, Christoph Hunkenschröder, Adrian Vetta |
| 2016 | On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm |
| 2016 | On the maximum quartet distance between phylogenetic trees. Noga Alon, Humberto Naves, Benny Sudakov |
| 2016 | On the switch Markov chain for perfect matchings. Martin E. Dyer, Mark Jerrum, Haiko Müller |
| 2016 | Online Contention Resolution Schemes. Moran Feldman, Ola Svensson, Rico Zenklusen |
| 2016 | Online Degree-Bounded Steiner Network Design. Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat |
| 2016 | Online Pricing with Impatient Bidders. Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang |
| 2016 | Packing Small Vectors. Yossi Azar, Ilan Reuven Cohen, Amos Fiat, Alan Roytman |
| 2016 | Partial Resampling to Approximate Covering Integer Programs. Antares Chen, David G. Harris, Aravind Srinivasan |
| 2016 | Permutation patterns are hard to count. Scott Garrabrant, Igor Pak |
| 2016 | Persistent Homology and Nested Dissection. Michael Kerber, Donald R. Sheehy, Primoz Skraba |
| 2016 | Phase Transitions in Group Testing. Jonathan Scarlett, Volkan Cevher |
| 2016 | Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 Robert Krauthgamer |
| 2016 | Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee. Shivam Garg, Geevarghese Philip |
| 2016 | Random-Cluster Dynamics in ℤ Antonio Blanca, Alistair Sinclair |
| 2016 | Range Predecessor and Lempel-Ziv Parsing. Djamal Belazzougui, Simon J. Puglisi |
| 2016 | Recovery and Rigidity in a Regular Stochastic Block Model. Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, Linh V. Tran |
| 2016 | Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics. T.-H. Hubert Chan, Shaofeng H.-C. Jiang |
| 2016 | Robust positioning patterns. Ross Berkowitz, Swastik Kopparty |
| 2016 | Sampling on Lattices with Free Boundary Conditions Using Randomized Extensions. Sarah Cannon, Dana Randall |
| 2016 | Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time. Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley |
| 2016 | Simple Pricing Schemes For Consumers With Evolving Values. Shuchi Chawla, Nikhil R. Devanur, Anna R. Karlin, Balasubramanian Sivan |
| 2016 | Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut. Chandra Chekuri, Vivek Madan |
| 2016 | Simpler, faster and shorter labels for distances in graphs. Stephen Alstrup, Cyril Gavoille, Esben Bistrup Halvorsen, Holger Petersen |
| 2016 | Sparse Approximation via Generating Point Sets. Avrim Blum, Sariel Har-Peled, Benjamin Raichel |
| 2016 | Sparsity and dimension. Gwenaël Joret, Piotr Micek, Veit Wiechert |
| 2016 | Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract). Constantinos Daskalakis, Sebastien Roch |
| 2016 | Stabilizing Consensus with Many Opinions. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan |
| 2016 | Subexponential parameterized algorithm for Interval Completion. Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michal Pilipczuk |
| 2016 | Subtree Isomorphism Revisited. Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir |
| 2016 | The Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya |
| 2016 | The Adversarial Noise Threshold for Distributed Protocols. William M. Hoza, Leonard J. Schulman |
| 2016 | The Complexity of All-switches Strategy Improvement. John Fearnley, Rahul Savani |
| 2016 | The Power of Two Choices with Simple Tabulation. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |
| 2016 | The Restricted Isometry Property of Subsampled Fourier Matrices. Ishay Haviv, Oded Regev |
| 2016 | The complexity of approximately counting in 2-spin systems on Andreas Galanis, Leslie Ann Goldberg |
| 2016 | The matching problem has no small symmetric SDP. Gábor Braun, Jonah Brown-Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz, Daniel Zink |
| 2016 | Tight Bounds for Graph Homomorphism and Subgraph Isomorphism. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala |
| 2016 | Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. Xi Chen, Jinyu Xie |
| 2016 | Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. Radu Curticapean, Dániel Marx |
| 2016 | Time vs. Information Tradeoffs for Leader Election in Anonymous Trees. Christian Glacet, Avery Miller, Andrzej Pelc |
| 2016 | Towards Optimal Algorithms for Prediction with Expert Advice. Nick Gravin, Yuval Peres, Balasubramanian Sivan |
| 2016 | Towards Optimal Deterministic Coding for Interactive Communication. Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson |
| 2016 | Treetopes and their Graphs. David Eppstein |
| 2016 | Undirected Graph Exploration with ⊝(log log Yann Disser, Jan Hackfeld, Max Klimm |
| 2016 | Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia |
| 2016 | Weak duality for packing edge-disjoint odd ( Ross Churchley, Bojan Mohar, Hehui Wu |
| 2016 | Weighted SGD for Jiyan Yang, Yinlam Chow, Christopher Ré, Michael W. Mahoney |
| 2016 | Weighted dynamic finger in binary search trees. John Iacono, Stefan Langerman |
| 2016 | Windrose Planarity: Embedding Graphs with Direction-Constrained Edges. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Valentino Di Donato, Philipp Kindermann, Günter Rote, Ignaz Rutter |