| 2019 | Fiat-Shamir: from practice to theory. | Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs |
| 2019 | Algebraic approach to promise constraint satisfaction. | Jakub Buln, Andrei A. Krokhin, Jakub Oprsal |
| 2019 | Competitively chasing convex bodies. | Sbastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke |
| 2019 | Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. | Karl Bringmann, Marvin Knnemann, Karol Wegrzycki |
| 2019 | Learning restricted Boltzmann machines via influence maximization. | Guy Bresler, Frederic Koehler, Ankur Moitra |
| 2019 | CSPs with global modular constraints: algorithms and hardness via polynomial representations. | Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami |
| 2019 | Bridging between 0/1 and linear programming via random walks. | Joshua Brakensiek, Venkatesan Guruswami |
| 2019 | 1+ | Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin |
| 2019 | Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. | Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, Henry Yuen |
| 2019 | Weak zero-knowledge beyond the black-box barrier. | Nir Bitansky, Dakshita Khurana, Omer Paneth |
| 2019 | Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. | Hedyeh Beyhaghi, S. Matthew Weinberg |
| 2019 | Decremental strongly-connected components and single-source reachability in near-linear time. | Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen |
| 2019 | Distributed exact weighted all-pairs shortest paths in near-linear time. | Aaron Bernstein, Danupon Nanongkai |
| 2019 | Achieving optimal backlog in multi-processor cup games. | Michael A. Bender, Martin Farach-Colton, William Kuszmaul |
| 2019 | Planar graphs of bounded degree have bounded queue number. | Michael A. Bekos, Henry Frster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt |
| 2019 | Oblivious dimension reduction for | Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris Schwiegelshohn |
| 2019 | On a generalization of iterated and randomized rounding. | Nikhil Bansal |
| 2019 | An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2019 | Quantum state certification. | Costin Badescu, Ryan O'Donnell, John Wright |
| 2019 | The communication complexity of local search. | Yakov Babichenko, Shahar Dobzinski, Noam Nisan |
| 2019 | Canonical form for graphs in quasipolynomial time: preliminary report. | Lszl Babai |
| 2019 | A universal sampling method for reconstructing signals with simple Fourier transforms. | Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh |
| 2019 | Polynomial pass lower bounds for graph streaming algorithms. | Sepehr Assadi, Yu Chen, Sanjeev Khanna |
| 2019 | Quantum weak coin flipping. | Atul Singh Arora, Jrmie Roland, Stephan Weis |
| 2019 | Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant |