| 2019 | Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. | Peter Brgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2019 | Quantum Advantage with Noisy Shallow Circuits in 3D. | Sergey Bravyi, David Gosset, Robert Knig, Marco Tomamichel |
| 2019 | Sensitive Distance and Reachability Oracles for Large Batch Updates. | Jan van den Brand, Thatchaphol Saranurak |
| 2019 | Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. | Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak |
| 2019 | Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. | Jan van den Brand, Danupon Nanongkai |
| 2019 | The Average-Case Complexity of Counting Cliques in Erdős-Rnyi Hypergraphs. | Enric Boix-Adser, Matthew S. Brennan, Guy Bresler |
| 2019 | An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices. | Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao |
| 2019 | A New Deterministic Algorithm for Dynamic Set Cover. | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
| 2019 | Residual Based Sampling for Online Low Rank Approximation. | Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, Morteza Zadimoghaddam |
| 2019 | Smoothed Analysis in Unsupervised Learning via Decoupling. | Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan |
| 2019 | Finding Monotone Patterns in Sublinear Time. | Omri Ben-Eliezer, Clment L. Canonne, Shoham Letzter, Erik Waingarten |
| 2019 | Exponentially Faster Massively Parallel Maximal Matching. | Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris |
| 2019 | Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan |
| 2019 | Near-Optimal Massively Parallel Graph Connectivity. | Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni |
| 2019 | Breaking of 1RSB in Random Regular MAX-NAE-SAT. | Zsolt Bartha, Nike Sun, Yumeng Zhang |
| 2019 | New Notions and Constructions of Sparsification for Graphs and Hypergraphs. | Nikhil Bansal, Ola Svensson, Luca Trevisan |
| 2019 | Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. | Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha |
| 2019 | Lower Bounds for Maximal Matchings and Maximal Independent Sets. | Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikal Rabie, Jukka Suomela |
| 2019 | General Framework for Metric Optimization Problems with Delay or with Deadlines. | Yossi Azar, Noam Touitou |
| 2019 | Automating Resolution is NP-Hard. | Albert Atserias, Moritz Mller |
| 2019 | Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders. | Sepehr Assadi, Sahil Singla |
| 2019 | Fast Uniform Generation of Random Graphs with Given Degree Sequences. | Andrii Arman, Pu Gao, Nicholas C. Wormald |
| 2019 | Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error. | Benny Applebaum, Eliran Kachlon |
| 2019 | Quantum Log-Approximate-Rank Conjecture is Also False. | Anurag Anshu, Naresh Goud Boddu, Dave Touchette |
| 2019 | A Tight Analysis of Bethe Approximation for Permanent. | Nima Anari, Alireza Rezaei |