| 2019 | (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. Vasileios Nakos, Zhao Song, Zhengyu Wang |
| 2019 | 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 David Zuckerman |
| 2019 | A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs). Artur Czumaj, Christian Sohler |
| 2019 | A Deterministic Algorithm for Counting Colorings with 2-Delta Colors. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava |
| 2019 | A New Deterministic Algorithm for Dynamic Set Cover. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
| 2019 | A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk |
| 2019 | A Quantum Query Complexity Trichotomy for Regular Languages. Scott Aaronson, Daniel Grier, Luke Schaeffer |
| 2019 | A Tight Analysis of Bethe Approximation for Permanent. Nima Anari, Alireza Rezaei |
| 2019 | Adversarial Bandits with Knapsacks. Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, Aleksandrs Slivkins |
| 2019 | Agreement Testing Theorems on Layered Set Systems. Yotam Dikstein, Irit Dinur |
| 2019 | An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices. Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao |
| 2019 | Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani |
| 2019 | Approximation Algorithms for LCS and LIS with Truly Improved Running Times. Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun |
| 2019 | Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg |
| 2019 | Automating Resolution is NP-Hard. Albert Atserias, Moritz Müller |
| 2019 | Balancing Straight-Line Programs. Moses Ganardi, Artur Jez, Markus Lohrey |
| 2019 | Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha |
| 2019 | Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications. Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair |
| 2019 | Breaking of 1RSB in Random Regular MAX-NAE-SAT. Zsolt Bartha, Nike Sun, Yumeng Zhang |
| 2019 | Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits. Chao Tao, Qin Zhang, Yuan Zhou |
| 2019 | Computationally-Secure and Composable Remote State Preparation. Alexandru Gheorghiu, Thomas Vidick |
| 2019 | Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. Mohsen Ghaffari, Fabian Kuhn, Jara Uitto |
| 2019 | Derandomization from Algebraic Hardness: Treading the Borders. Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon |
| 2019 | Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. David G. Harris |
| 2019 | Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. Jan van den Brand, Danupon Nanongkai |
| 2019 | Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak |
| 2019 | Efficient Construction of Rigid Matrices Using an NP Oracle. Josh Alman, Lijie Chen |
| 2019 | Efficient Truncated Statistics with Unknown Truncation. Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis |
| 2019 | Expander Graphs - Both Local and Global. Michael Chapman, Nati Linial, Yuval Peled |
| 2019 | Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. Makrand Sinha, Ronald de Wolf |
| 2019 | Exponentially Faster Massively Parallel Maximal Matching. Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris |
| 2019 | Fast Generalized DFTs for all Finite Groups. Chris Umans |
| 2019 | Fast Uniform Generation of Random Graphs with Given Degree Sequences. Andrii Arman, Pu Gao, Nicholas C. Wormald |
| 2019 | Faster Matroid Intersection. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong |
| 2019 | Faster Minimum k-cut of a Simple Graph. Jason Li |
| 2019 | Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk. Oren Mangoubi, Nisheeth K. Vishnoi |
| 2019 | Finding Monotone Patterns in Sublinear Time. Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten |
| 2019 | Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. Shiri Chechik, Tianyi Zhang |
| 2019 | Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan |
| 2019 | General Framework for Metric Optimization Problems with Delay or with Deadlines. Yossi Azar, Noam Touitou |
| 2019 | Hardness Magnification for all Sparse NP Languages. Lijie Chen, Ce Jin, R. Ryan Williams |
| 2019 | How to Use Heuristics for Differential Privacy. Seth Neel, Aaron Roth, Zhiwei Steven Wu |
| 2019 | Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders. Sepehr Assadi, Sahil Singla |
| 2019 | Inapproximability of Clustering in Lp Metrics. Vincent Cohen-Addad, Karthik C. S. |
| 2019 | Junta Correlation is Testable. Anindya De, Elchanan Mossel, Joe Neeman |
| 2019 | Laconic Conditional Disclosure of Secrets and Applications. Nico Döttling, Sanjam Garg, Vipul Goyal, Giulio Malavolta |
| 2019 | Leakage-Resilient Secret Sharing Against Colluding Parties. Ashutosh Kumar, Raghu Meka, Amit Sahai |
| 2019 | Learning from Outcomes: Evidence-Based Rankings. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
| 2019 | Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces. Luke Postle |
| 2019 | Lower Bounds for Maximal Matchings and Maximal Independent Sets. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela |
| 2019 | Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions. Mary Cryan, Heng Guo, Giorgos Mousa |
| 2019 | More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson |
| 2019 | Multi-resolution Hashing for Fast Pairwise Summations. Moses Charikar, Paris Siminelakis |
| 2019 | NEEXP is Contained in MIP. Anand Natarajan, John Wright |
| 2019 | Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. David Saulpic, Vincent Cohen-Addad, Andreas Emil Feldmann |
| 2019 | Near-Optimal Massively Parallel Graph Connectivity. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni |
| 2019 | New Notions and Constructions of Sparsification for Graphs and Hypergraphs. Nikhil Bansal, Ola Svensson, Luca Trevisan |
| 2019 | Noise Sensitivity on the p -Biased Hypercube. Noam Lifshitz, Dor Minzer |
| 2019 | Non-Malleable Commitments using Goldreich-Levin List Decoding. Vipul Goyal, Silas Richelson |
| 2019 | Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. Lijie Chen |
| 2019 | Online Matching with General Arrivals. Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc |
| 2019 | Optimal Document Exchange and New Codes for Insertions and Deletions. Bernhard Haeupler |
| 2019 | Optimization of the Sherrington-Kirkpatrick Hamiltonian. Andrea Montanari |
| 2019 | Parallel Reachability in Almost Linear Work and Square Root Depth. Yang P. Liu, Arun Jambulapati, Aaron Sidford |
| 2019 | Parametric Shortest Paths in Planar Graphs. Kshitij Gajjar, Jaikumar Radhakrishnan |
| 2019 | Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. Alex Bredariol Grilo, William Slofstra, Henry Yuen |
| 2019 | Planar Graphs have Bounded Queue-Number. Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood |
| 2019 | Polylogarithmic Guarantees for Generalized Reordering Buffer Management. Matthias Englert, Harald Räcke, Richard Stotz |
| 2019 | Polynomial Calculus Space and Resolution Width. Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen |
| 2019 | Quantum Advantage with Noisy Shallow Circuits in 3D. Sergey Bravyi, David Gosset, Robert König, Marco Tomamichel |
| 2019 | Quantum Log-Approximate-Rank Conjecture is Also False. Anurag Anshu, Naresh Goud Boddu, Dave Touchette |
| 2019 | Quasilinear Time List-Decodable Codes for Space Bounded Channels. Jad Silbak, Swastik Kopparty, Ronen Shaltiel |
| 2019 | Radio Network Coding Requires Logarithmic Overhead. Klim Efremenko, Gillat Kol, Raghuvansh Saxena |
| 2019 | Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick |
| 2019 | Reed-Muller Codes Polarize. Emmanuel Abbe, Min Ye |
| 2019 | Residual Based Sampling for Online Low Rank Approximation. Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, Morteza Zadimoghaddam |
| 2019 | SETH-Hardness of Coding Problems. Noah Stephens-Davidowitz, Vinod Vaikuntanathan |
| 2019 | Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error. Benny Applebaum, Eliran Kachlon |
| 2019 | Sensitive Distance and Reachability Oracles for Large Batch Updates. Jan van den Brand, Thatchaphol Saranurak |
| 2019 | Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers. Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg |
| 2019 | Smoothed Analysis in Unsupervised Learning via Decoupling. Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan |
| 2019 | Spectral Analysis of Matrix Scaling and Operator Scaling. Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran |
| 2019 | Stoquastic PCP vs. Randomness. Dorit Aharonov, Alex Bredariol Grilo |
| 2019 | Sublinear Algorithms for Gap Edit Distance. Elazar Goldenberg, Robert Krauthgamer, Barna Saha |
| 2019 | The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs. Enric Boix-Adserà, Matthew S. Brennan, Guy Bresler |
| 2019 | The Complexity of 3-Colouring H-Colourable Graphs. Andrei A. Krokhin, Jakub Oprsal |
| 2019 | The Kikuchi Hierarchy and Tensor PCA. Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore |
| 2019 | The Role of Interactivity in Local Differential Privacy. Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth |
| 2019 | Tight Bounds for Online Edge Coloring. Ilan Reuven Cohen, Binghui Peng, David Wajc |
| 2019 | Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2019 | Truly Optimal Euclidean Spanners. Hung Le, Shay Solomon |
| 2019 | Waring Rank, Parameterized and Exact Algorithms. Kevin Pratt |
| 2019 | Why are Proof Complexity Lower Bounds Hard? Ján Pich, Rahul Santhanam |