| 2016 | A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. Elaine Levey, Thomas Rothvoss |
| 2016 | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx |
| 2016 | A cost function for similarity-based hierarchical clustering. Sanjoy Dasgupta |
| 2016 | A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2016 | A discrete and bounded envy-free cake cutting protocol for four agents. Haris Aziz, Simon Mackenzie |
| 2016 | A duality based unified approach to Bayesian mechanism design. Yang Cai, Nikhil R. Devanur, S. Matthew Weinberg |
| 2016 | A lower bound for the distributed Lovász local lemma. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto |
| 2016 | A polynomial lower bound for testing monotonicity. Aleksandrs Belovs, Eric Blais |
| 2016 | A size-free CLT for poisson multinomials and its applications. Constantinos Daskalakis, Anindya De, Gautam Kamath, Christos Tzamos |
| 2016 | A tight space bound for consensus. Leqi Zhu |
| 2016 | Algebraic attacks against random local functions and their countermeasures. Benny Applebaum, Shachar Lovett |
| 2016 | Algorithmic Bayesian persuasion. Shaddin Dughmi, Haifeng Xu |
| 2016 | Algorithmic stability for adaptive data analysis. Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan R. Ullman |
| 2016 | Almost tight bounds for eliminating depth cycles in three dimensions. Boris Aronov, Micha Sharir |
| 2016 | Approximating connectivity domination in weighted bounded-genus graphs. Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld |
| 2016 | Base collapse of holographic algorithms. Mingji Xia |
| 2016 | Basis collapse for holographic algorithms over all domain sizes. Sitan Chen |
| 2016 | Beating CountSketch for heavy hitters in insertion streams. Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff |
| 2016 | Beyond matroids: secretary problem and prophet inequality with general constraints. Aviad Rubinstein |
| 2016 | Bipartite perfect matching is in quasi-NC. Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf |
| 2016 | Bounded degree cosystolic expanders of every dimension. Shai Evra, Tali Kaufman |
| 2016 | Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. Shahar Dobzinski |
| 2016 | Candidate hard unique game. Subhash Khot, Dana Moshkovitz |
| 2016 | Cell-probe lower bounds for dynamic problems via a new communication model. Huacheng Yu |
| 2016 | Classical verification of quantum proofs. Zhengfeng Ji |
| 2016 | Communication lower bounds for statistical estimation problems via a distributed data processing inequality. Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff |
| 2016 | Complexity theoretic limitations on learning halfspaces. Amit Daniely |
| 2016 | Constant-rate coding for multiparty interactive communication is impossible. Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler |
| 2016 | Constant-round interactive proofs for delegating computation. Omer Reingold, Guy N. Rothblum, Ron D. Rothblum |
| 2016 | Contention resolution with log-logstar channel accesses. Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young |
| 2016 | Deterministic and probabilistic binary search in graphs. Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal |
| 2016 | Deterministic decremental single source shortest paths: beyond the o(mn) bound. Aaron Bernstein, Shiri Chechik |
| 2016 | Distributed (∆+1)-coloring in sublogarithmic rounds. David G. Harris, Johannes Schneider, Hsin-Hao Su |
| 2016 | Do prices coordinate markets? Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth, Rakesh Vohra |
| 2016 | Efficient quantum tomography. Ryan O'Donnell, John Wright |
| 2016 | Efficiently decoding Reed-Muller codes from random errors. Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk |
| 2016 | Entangled simultaneity versus classical interactivity in communication complexity. Dmitry Gavinsky |
| 2016 | Enumerating parametric global minimum cuts by random interleaving. David R. Karger |
| 2016 | Exact algorithms via monotone local search. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh |
| 2016 | Explicit two-source extractors and resilient functions. Eshan Chattopadhyay, David Zuckerman |
| 2016 | Exponential separation of communication and external information. Anat Ganor, Gillat Kol, Ran Raz |
| 2016 | Extractors for sumset sources. Eshan Chattopadhyay, Xin Li |
| 2016 | Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer |
| 2016 | Fault tolerant subgraph for single source reachability: generic and optimal. Surender Baswana, Keerti Choudhary, Liam Roditty |
| 2016 | Geometric median in nearly linear time. Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
| 2016 | Graph isomorphism in quasipolynomial time [extended abstract]. László Babai |
| 2016 | High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf |
| 2016 | How robust are reconstruction thresholds for community detection? Ankur Moitra, William Perry, Alexander S. Wein |
| 2016 | Improved approximation for node-disjoint paths in planar graphs. Julia Chuzhoy, David H. K. Kim, Shi Li |
| 2016 | Instance optimal learning of discrete distributions. Gregory Valiant, Paul Valiant |
| 2016 | Interactive compression for product distributions. Gillat Kol |
| 2016 | Lift-and-round to improve weighted completion time on unrelated machines. Nikhil Bansal, Aravind Srinivasan, Ola Svensson |
| 2016 | Matrix rigidity of random toeplitz matrices. Oded Goldreich, Avishay Tal |
| 2016 | Maximizing determinants under partition constraints. Aleksandar Nikolov, Mohit Singh |
| 2016 | Near-optimal small-depth lower bounds for small distance connectivity. Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan |
| 2016 | New deterministic approximation algorithms for fully dynamic matching. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
| 2016 | Non-malleable extractors and codes, with their many tampered extensions. Eshan Chattopadhyay, Vipul Goyal, Xin Li |
| 2016 | On approximating functions of the singular values in a stream. Yi Li, David P. Woodruff |
| 2016 | On the effect of randomness on planted 3-coloring models. Roee David, Uriel Feige |
| 2016 | On the size of homogeneous and of depth four formulas with low individual degree. Neeraj Kayal, Chandan Saha, Sébastien Tavenas |
| 2016 | Online matching: haste makes waste! Yuval Emek, Shay Kutten, Roger Wattenhofer |
| 2016 | Optimal principal component analysis in distributed and streaming models. Christos Boutsidis, David P. Woodruff, Peilin Zhong |
| 2016 | Parallel algorithms for select and partition with noisy comparisons. Mark Braverman, Jieming Mao, S. Matthew Weinberg |
| 2016 | Parallel exhaustive search without coordination. Pierre Fraigniaud, Amos Korman, Yoav Rodeh |
| 2016 | Poly-logarithmic Frege depth lower bounds via an expander switching lemma. Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2016 | Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 Daniel Wichs, Yishay Mansour |
| 2016 | Ramanujan coverings of graphs. Chris Hall, Doron Puder, William F. Sawin |
| 2016 | Reed-Muller codes achieve capacity on erasure channels. Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rüdiger L. Urbanke |
| 2016 | Relating two property testing models for bounded degree directed graphs. Artur Czumaj, Pan Peng, Christian Sohler |
| 2016 | Repairing Reed-solomon codes. Venkatesan Guruswami, Mary Wootters |
| 2016 | Routing under balance. Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
| 2016 | Sample-optimal tomography of quantum states. Jeongwan Haah, Aram W. Harrow, Zheng-Feng Ji, Xiaodi Wu, Nengkun Yu |
| 2016 | Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. Gilad Asharov, Moni Naor, Gil Segev, Ido Shahaf |
| 2016 | Semidefinite programs on sparse random graphs and their application to community detection. Andrea Montanari, Subhabrata Sen |
| 2016 | Separating subadditive euclidean functionals. Alan M. Frieze, Wesley Pegden |
| 2016 | Separations in query complexity based on pointer functions. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs |
| 2016 | Separations in query complexity using cheat sheets. Scott Aaronson, Shalev Ben-David, Robin Kothari |
| 2016 | Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams |
| 2016 | Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. Michael Kapralov |
| 2016 | Sparsified Cholesky and multigrid solvers for connection laplacians. Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman |
| 2016 | Streaming algorithms for embedding and computing edit distance in the low distance regime. Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký |
| 2016 | Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. Daniel M. Kane, Ryan Williams |
| 2016 | Textbook non-malleable commitments. Vipul Goyal, Omkant Pandey, Silas Richelson |
| 2016 | The 4/3 additive spanner exponent is tight. Amir Abboud, Greg Bodwin |
| 2016 | The computational power of optimization in online learning. Elad Hazan, Tomer Koren |
| 2016 | The fourier transform of poisson multinomial distributions and its algorithmic applications. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
| 2016 | The price of anarchy in large games. Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis |
| 2016 | The sample complexity of auctions with side information. Nikhil R. Devanur, Zhiyi Huang, Christos-Alexandros Psomas |
| 2016 | Tight bounds for single-pass streaming complexity of the set cover problem. Sepehr Assadi, Sanjeev Khanna, Yang Li |
| 2016 | Two-source dispersers for polylogarithmic entropy and improved ramsey graphs. Gil Cohen |
| 2016 | Watch and learn: optimizing from revealed preferences feedback. Aaron Roth, Jonathan R. Ullman, Zhiwei Steven Wu |
| 2016 | Watermarking cryptographic capabilities. Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs |
| 2016 | Weighted low rank approximations with provable guarantees. Ilya P. Razenshteyn, Zhao Song, David P. Woodruff |