| 2019 | An exponential lower bound on the sub-packetization of MSR codes. | Omar Alrabiah, Venkatesan Guruswami |
| 2019 | Private PAC learning implies finite Littlestone dimension. | Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran |
| 2019 | Why extension-based proofs fail. | Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu |
| 2019 | Dynamic set cover: improved algorithms and lower bounds. | Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha |
| 2019 | Gentle measurement of quantum states and differential privacy. | Scott Aaronson, Guy N. Rothblum |
| 2019 | Quantum Lovsz local lemma: Shearer's bound is tight. | Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang |
| 2019 | Random walks and forbidden minors II: a poly( | Akash Kumar, C. Seshadhri, Andrew Stolman |
| 2019 | Unconstrained submodular maximization with constant adaptive complexity. | Lin Chen, Moran Feldman, Amin Karbasi |
| 2019 | Private selection from private candidates. | Jingcheng Liu, Kunal Talwar |
| 2019 | Untitled record | Fabrizio Grandoni, Bundit Laekhanukit, Shi Li |
| 2019 | Lower bounds for external memory integer sorting via network coding. | Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi |
| 2018 | Quantified derandomization of linear threshold circuits. | Roei Tell |
| 2018 | A constant-factor approximation algorithm for the asymmetric traveling salesman problem. | Ola Svensson, Jakub Tarnawski, Lszl A. Vgh |
| 2018 | On the parameterized complexity of approximating dominating set. | Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi |
| 2018 | Tight query complexity lower bounds for PCA via finite sample deformed wigner law. | Max Simchowitz, Ahmed El Alaoui, Benjamin Recht |
| 2018 | Algorithmic polynomials. | Alexander A. Sherstov |
| 2018 | Prediction with a short memory. | Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant |
| 2018 | An almost-linear time algorithm for uniform random spanning tree generation. | Aaron Schild |
| 2018 | Hardness of approximate nearest neighbor search. | Aviad Rubinstein |
| 2018 | Lifting nullstellensatz to monotone span programs over any field. | Toniann Pitassi, Robert Robere |
| 2018 | The query complexity of graph isomorphism: bypassing distribution testing lower bounds. | Krzysztof Onak, Xiaorui Sun |
| 2018 | Shape of diffusion and size of monochromatic region of a two-dimensional spin system. | Hamed Omidvar, Massimo Franceschetti |
| 2018 | An exponential lower bound for individualization-refinement algorithms for graph isomorphism. | Daniel Neuen, Pascal Schweitzer |
| 2018 | Sparse Kneser graphs are Hamiltonian. | Torsten Mtze, Jerri Nummenpalo, Bartosz Walczak |
| 2018 | Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. | Cody Murray, R. Ryan Williams |