| 2019 | 1+ Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Saeed Seddighin |
| 2019 | A fixed-depth size-hierarchy theorem for AC Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh |
| 2019 | A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. Julia Chuzhoy, Sanjeev Khanna |
| 2019 | A quantum-inspired classical algorithm for recommendation systems. Ewin Tang |
| 2019 | A strongly polynomial algorithm for linear exchange markets. Jugal Garg, László A. Végh |
| 2019 | A unifying method for the design of algorithms canonizing combinatorial objects. Pascal Schweitzer, Daniel Wiebking |
| 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 | Achieving optimal backlog in multi-processor cup games. Michael A. Bender, Martin Farach-Colton, William Kuszmaul |
| 2019 | Algebraic approach to promise constraint satisfaction. Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal |
| 2019 | Algorithmic Pirogov-Sinai theory. Tyler Helmuth, Will Perkins, Guus Regts |
| 2019 | Almost optimal distance oracles for planar graphs. Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2019 | An exponential lower bound on the sub-packetization of MSR codes. Omar Alrabiah, Venkatesan Guruswami |
| 2019 | An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2019 | An optimal space lower bound for approximating MAX-CUT. Michael Kapralov, Dmitry Krachun |
| 2019 | Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. Karl Bringmann, Marvin Künnemann, Karol Wegrzycki |
| 2019 | Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions. André Linhares, Chaitanya Swamy |
| 2019 | Approximation algorithms for minimum norm and ordered optimization problems. Deeparnab Chakrabarty, Chaitanya Swamy |
| 2019 | Beyond the low-degree algorithm: mixtures of subcubes and their applications. Sitan Chen, Ankur Moitra |
| 2019 | Bootstrapping results for threshold circuits "just beyond" known lower bounds. Lijie Chen, Roei Tell |
| 2019 | Breaking quadratic time for small vertex connectivity and an approximation scheme. Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2019 | Bridging between 0/1 and linear programming via random walks. Joshua Brakensiek, Venkatesan Guruswami |
| 2019 | CSPs with global modular constraints: algorithms and hardness via polynomial representations. Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami |
| 2019 | Canonical form for graphs in quasipolynomial time: preliminary report. László Babai |
| 2019 | Capacity lower bound for the Ising perceptron. Jian Ding, Nike Sun |
| 2019 | Communication complexity of estimating correlations. Uri Hadar, Jingbo Liu, Yury Polyanskiy, Ofer Shayevitz |
| 2019 | Competitively chasing convex bodies. Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke |
| 2019 | Computing quartet distance is equivalent to counting 4-cycles. Bartlomiej Dudek, Pawel Gawrychowski |
| 2019 | DNF sparsification beyond sunflowers. Shachar Lovett, Jiapeng Zhang |
| 2019 | Decremental strongly-connected components and single-source reachability in near-linear time. Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen |
| 2019 | Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). Ilias Diakonikolas, Daniel M. Kane |
| 2019 | Distributed edge connectivity in sublinear time. Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak |
| 2019 | Distributed exact weighted all-pairs shortest paths in near-linear time. Aaron Bernstein, Danupon Nanongkai |
| 2019 | Dynamic low-stretch trees via dynamic low-diameter decompositions. Sebastian Forster, Gramoz Goranci |
| 2019 | Dynamic sampling from graphical models. Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin |
| 2019 | Dynamic set cover: improved algorithms and lower bounds. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha |
| 2019 | Efficient profile maximum likelihood for universal symmetric property estimation. Moses Charikar, Kirankumar Shiragur, Aaron Sidford |
| 2019 | Explicit N-vertex graphs with maximum degree K and diameter [1+o(1)] log Michael Capalbo |
| 2019 | Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal |
| 2019 | Faster Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick |
| 2019 | Fiat-Shamir: from practice to theory. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, Daniel Wichs |
| 2019 | Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum |
| 2019 | Flows in almost linear time via adaptive preconditioning. Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang |
| 2019 | Fooling polytopes. Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2019 | Fully dynamic spectral vertex sparsifiers and applications. David Durfee, Yu Gao, Gramoz Goranci, Richard Peng |
| 2019 | Gentle measurement of quantum states and differential privacy. Scott Aaronson, Guy N. Rothblum |
| 2019 | Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, Henry Yuen |
| 2019 | Graph pattern detection: hardness for all induced patterns and faster non-induced cycles. Mina Dalirrooyfard, Thuy-Duong Vuong, Virginia Vassilevska Williams |
| 2019 | Hamiltonian simulation with nearly optimal dependence on spectral norm. Guang Hao Low |
| 2019 | How to delegate computations publicly. Yael Tauman Kalai, Omer Paneth, Lisa Yang |
| 2019 | Learning restricted Boltzmann machines via influence maximization. Guy Bresler, Frederic Koehler, Ankur Moitra |
| 2019 | Local decodability of the Burrows-Wheeler transform. Sandip Sinha, Omri Weinstein |
| 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 |
| 2019 | Lower bounds for external memory integer sorting via network coding. Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi |
| 2019 | Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. Vishesh Jain, Frederic Koehler, Andrej Risteski |
| 2019 | Memory-sample tradeoffs for linear regression with small error. Vatsal Sharan, Aaron Sidford, Gregory Valiant |
| 2019 | Near-linear time insertion-deletion codes and (1+ Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi |
| 2019 | Near-optimal lower bounds on the threshold degree and sign-rank of AC Alexander A. Sherstov, Pei Wu |
| 2019 | New polynomial delay bounds for maximal subgraph enumeration by proximity search. Alessio Conte, Takeaki Uno |
| 2019 | Non-Gaussian component analysis using entropy methods. Navin Goyal, Abhishek Shetty |
| 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 | On approximating the covering radius and finding dense lattice subspaces. Daniel Dadush |
| 2019 | On the approximation resistance of balanced linear threshold functions. Aaron Potechin |
| 2019 | Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. Hedyeh Beyhaghi, S. Matthew Weinberg |
| 2019 | Optimal sequence length requirements for phylogenetic tree reconstruction with indels. Arun Ganesh, Qiuyi (Richard) Zhang |
| 2019 | Optimal succinct rank data structure via approximate nonnegative tensor decomposition. Huacheng Yu |
| 2019 | Optimal terminal dimensionality reduction in Euclidean space. Shyam Narayanan, Jelani Nelson |
| 2019 | Oracle separation of BQP and PH. Ran Raz, Avishay Tal |
| 2019 | Parallelizing greedy for submodular set function maximization in matroids and beyond. Chandra Chekuri, Kent Quanrud |
| 2019 | Performance of Johnson-Lindenstrauss transform for Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn |
| 2019 | Planar diameter via metric compression. Jason Li, Merav Parter |
| 2019 | Planar graphs of bounded degree have bounded queue number. Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt |
| 2019 | Planar point sets determine many pairwise crossing segments. János Pach, Natan Rubin, Gábor Tardos |
| 2019 | Polylogarithmic approximation for Euler genus on bounded degree graphs. Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2019 | Polynomial pass lower bounds for graph streaming algorithms. Sepehr Assadi, Yu Chen, Sanjeev Khanna |
| 2019 | Private PAC learning implies finite Littlestone dimension. Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran |
| 2019 | Private selection from private candidates. Jingcheng Liu, Kunal Talwar |
| 2019 | Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. Moses Charikar, Edith Cohen |
| 2019 | Pseudorandom generators for width-3 branching programs. Raghu Meka, Omer Reingold, Avishay Tal |
| 2019 | Quantum Lovász local lemma: Shearer's bound is tight. Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang |
| 2019 | Quantum proof systems for iterated exponential time, and beyond. Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen |
| 2019 | Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe |
| 2019 | Quantum state certification. Costin Badescu, Ryan O'Donnell, John Wright |
| 2019 | Quantum weak coin flipping. Atul Singh Arora, Jérémie Roland, Stephan Weis |
| 2019 | Random walks and forbidden minors II: a poly( Akash Kumar, C. Seshadhri, Andrew Stolman |
| 2019 | Reconstruction of non-degenerate homogeneous depth three circuits. Neeraj Kayal, Chandan Saha |
| 2019 | Regression from dependent observations. Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas |
| 2019 | Separating monotone VP and VNP. Amir Yehudayoff |
| 2019 | Settling the sample complexity of single-parameter revenue maximization. Chenghao Guo, Zhiyi Huang, Xinzhi Zhang |
| 2019 | Solving linear programs in the current matrix multiplication time. Michael B. Cohen, Yin Tat Lee, Zhao Song |
| 2019 | Spectral methods from tensor networks. Ankur Moitra, Alexander S. Wein |
| 2019 | Static data structure lower bounds imply rigidity. Zeev Dvir, Alexander Golovnev, Omri Weinstein |
| 2019 | String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. Dominik Kempa, Tomasz Kociumaka |
| 2019 | Stronger l Vasileios Nakos, Zhao Song |
| 2019 | Submodular maximization with matroid and packing constraints in parallel. Alina Ene, Huy L. Nguyen, Adrian Vladu |
| 2019 | Sylvester-Gallai type theorems for quadratic polynomials. Amir Shpilka |
| 2019 | Testing graphs against an unknown distribution. Lior Gishboliner, Asaf Shapira |
| 2019 | Testing graphs in vertex-distribution-free models. Oded Goldreich |
| 2019 | Testing unateness nearly optimally. Xi Chen, Erik Waingarten |
| 2019 | The communication complexity of local search. Yakov Babichenko, Shahar Dobzinski, Noam Nisan |
| 2019 | The complexity of splitting necklaces and bisecting ham sandwiches. Aris Filos-Ratsikas, Paul W. Goldberg |
| 2019 | The log-approximate-rank conjecture is false. Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif |
| 2019 | The number of minimum Anupam Gupta, Euiwoong Lee, Jason Li |
| 2019 | The online k-taxi problem. Christian Coester, Elias Koutsoupias |
| 2019 | The parallel repetition of non-signaling games: counterexamples and dichotomy. Justin Holmgren, Lisa Yang |
| 2019 | The reachability problem for Petri nets is not elementary. Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, Filip Mazowiecki |
| 2019 | The structure of optimal private tests for simple hypotheses. Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, Jonathan R. Ullman |
| 2019 | Tight approximation ratio of anonymous pricing. Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, Tao Xiao |
| 2019 | Towards the locality of Vizing's theorem. Hsin-Hao Su, Hoa T. Vu |
| 2019 | Unconstrained submodular maximization with constant adaptive complexity. Lin Chen, Moran Feldman, Amin Karbasi |
| 2019 | Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. Dylan M. McKay, Cody D. Murray, R. Ryan Williams |
| 2019 | Weak zero-knowledge beyond the black-box barrier. Nir Bitansky, Dakshita Khurana, Omer Paneth |
| 2019 | Why extension-based proofs fail. Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu |