| 2021 | (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. András Gilyén, Matthew B. Hastings, Umesh V. Vazirani |
| 2021 | A (2 + Lars Rohwedder, Andreas Wiese |
| 2021 | A (slightly) improved approximation algorithm for metric TSP. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2021 | A deterministic algorithm for the MST problem in constant rounds of congested clique. Krzysztof Nowicki |
| 2021 | A faster algorithm for solving general LPs. Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang |
| 2021 | A framework for dynamic matching in weighted graphs. Aaron Bernstein, Aditi Dudeja, Zachary Langley |
| 2021 | A framework for quadratic form maximization over convex sets through nonconvex relaxations. Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor |
| 2021 | A full complexity dichotomy for immanant families. Radu Curticapean |
| 2021 | A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. Sally Dong, Yin Tat Lee, Guanghao Ye |
| 2021 | A new algorithm for Euclidean shortest paths in the plane. Haitao Wang |
| 2021 | A new analysis of differential privacy's generalization guarantees (invited paper). Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Moshe Shenfeld |
| 2021 | A new coreset framework for clustering. Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn |
| 2021 | A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper). Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
| 2021 | A quasipolynomial (2 + Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li |
| 2021 | A theory of universal learning. Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff |
| 2021 | Adversarial laws of large numbers and optimal regret in online classification. Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev |
| 2021 | Algorithmic foundations for the diffraction limit. Sitan Chen, Ankur Moitra |
| 2021 | Almost optimal super-constant-pass streaming lower bounds for reachability. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu |
| 2021 | An improved derandomization of the switching lemma. Zander Kelley |
| 2021 | An optimal separation of randomized and Quantum query complexity. Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu |
| 2021 | Approximate Gomory-Hu tree is faster than Jason Li, Debmalya Panigrahi |
| 2021 | Approximating Nash social welfare under rado valuations. Jugal Garg, Edin Husic, László A. Végh |
| 2021 | Automating algebraic proof systems is NP-hard. Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov |
| 2021 | Average-case hardness of NP from exponential worst-case hardness assumptions. Shuichi Hirahara |
| 2021 | Bipartite perfect matching as a real polynomial. Gal Beniamini, Noam Nisan |
| 2021 | Boosting simple learners. Noga Alon, Alon Gonen, Elad Hazan, Shay Moran |
| 2021 | Breaking the quadratic barrier for matroid intersection. Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2021 | Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. Federica Cecchetto, Vera Traub, Rico Zenklusen |
| 2021 | Capacity lower bounds via productization. Leonid Gurvits, Jonathan Leake |
| 2021 | Chasing convex bodies with linear competitive ratio (invited paper). C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang |
| 2021 | Clan embeddings into trees, and low treewidth graphs. Arnold Filtser, Hung Le |
| 2021 | Climbing algorithms (invited talk). Leonid A. Levin |
| 2021 | Combinatorial Bernoulli factories: matchings, flows, and other polytopes. Rad Niazadeh, Renato Paes Leme, Jon Schneider |
| 2021 | Computational thinking in programming language and compiler design (keynote). Alfred V. Aho |
| 2021 | Constant approximating k-clique is w[1]-hard. Bingkai Lin |
| 2021 | Contextual search in the presence of irrational agents. Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert E. Schapire |
| 2021 | Continuous LWE. Joan Bruna, Oded Regev, Min Jae Song, Yi Tang |
| 2021 | Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity. Yanyi Liu, Rafael Pass |
| 2021 | Decoding multivariate multiplicity codes on product sets. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan |
| 2021 | Decremental all-pairs shortest paths in deterministic near-linear time. Julia Chuzhoy |
| 2021 | Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal |
| 2021 | Deterministic mincut in almost-linear time. Jason Li |
| 2021 | Discrepancy minimization via a self-balancing walk. Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney |
| 2021 | Distributed weighted min-cut in nearly-optimal time. Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2021 | Dynamic planar point location in optimal time. Yakov Nekrich |
| 2021 | Efficient and near-optimal algorithms for sampling connected subgraphs. Marco Bressan |
| 2021 | Efficient list-decoding with constant alphabet and list sizes. Zeyu Guo, Noga Ron-Zewi |
| 2021 | Efficient randomized DCAS. George Giakkoupis, Mehrdad Jafari Giv, Philipp Woelfel |
| 2021 | Efficient randomized distributed coloring in CONGEST. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan |
| 2021 | Efficient two-sided markets with limited information. Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser |
| 2021 | Efficiently learning halfspaces with Tsybakov noise. Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
| 2021 | Eliminating intermediate measurements in space-bounded Quantum computation. Bill Fefferman, Zachary Remscrim |
| 2021 | Entropy decay in the Swendsen-Wang dynamics on ℤ Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda |
| 2021 | Expander random walks: a Fourier-analytic approach. Gil Cohen, Noam Peri, Amnon Ta-Shma |
| 2021 | Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity. Ronen Shaltiel, Jad Silbak |
| 2021 | Exponential communication separations between notions of selfishness. Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao |
| 2021 | Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). Justin Holmgren, Alex Lombardi, Ron D. Rothblum |
| 2021 | Fiber bundle codes: breaking the Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell |
| 2021 | Finding large induced sparse subgraphs in Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski |
| 2021 | Flow time scheduling with uncertain processing time. Yossi Azar, Stefano Leonardi, Noam Touitou |
| 2021 | Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong |
| 2021 | Frozen 1-RSB structure of the symmetric Ising perceptron. Will Perkins, Changji Xu |
| 2021 | Fully dynamic approximation of LIS in polylogarithmic time. Pawel Gawrychowski, Wojciech Janczewski |
| 2021 | Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. Sepehr Assadi, Vishvajeet N |
| 2021 | Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization. Oren Mangoubi, Nisheeth K. Vishnoi |
| 2021 | Hardness of learning DNFs using halfspaces. Suprovat Ghoshal, Rishi Saket |
| 2021 | Hop-constrained oblivious routing. Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic |
| 2021 | How asymmetry helps buffer management: achieving optimal tail size in cup games. William Kuszmaul |
| 2021 | How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, Ellen Vitercik |
| 2021 | Improved Quantum data analysis. Costin Badescu, Ryan O'Donnell |
| 2021 | Improved dynamic algorithms for longest increasing subsequence. Tomasz Kociumaka, Saeed Seddighin |
| 2021 | Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. Jesper Nederlof, Karol Wegrzycki |
| 2021 | Indistinguishability obfuscation from circular security. Romain Gay, Rafael Pass |
| 2021 | Indistinguishability obfuscation from well-founded assumptions. Aayush Jain, Huijia Lin, Amit Sahai |
| 2021 | Information theoretic limits of cardinality estimation: Fisher meets Shannon. Seth Pettie, Dingyu Wang |
| 2021 | Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. Lijie Chen, Xin Lyu |
| 2021 | Iterated lower bound formulas: a diagonalization-based approach to proof complexity. Rahul Santhanam, Iddo Tzameret |
| 2021 | Kronecker products, low-depth circuits, and matrix rigidity. Josh Alman |
| 2021 | Learnability can be independent of set theory (invited paper). Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff |
| 2021 | Learning Ising models from one or multiple samples. Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros |
| 2021 | Linear bandits with limited adaptivity and learning distributional optimal design. Yufei Ruan, Jiaqi Yang, Yuan Zhou |
| 2021 | Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper). Isaac Grosof, Ziv Scully, Mor Harchol-Balter |
| 2021 | Load balancing with dynamic set of balls and bins. Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup |
| 2021 | Local concentration inequalities and Tomaszewski's conjecture. Nathan Keller, Ohad Klein |
| 2021 | Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong |
| 2021 | Log-concave polynomials in theory and applications (tutorial). Nima Anari, Cynthia Vinzant |
| 2021 | Log-rank and lifting for AND-functions. Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan |
| 2021 | Lower bounds for monotone arithmetic circuits via communication complexity. Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay |
| 2021 | Minimum cost flows, MDPs, and ℓ Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang |
| 2021 | Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. Yair Bartal, Lee-Ad Gottlieb |
| 2021 | Near-linear time decoding of Ta-Shma's codes via splittable regularity. Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2021 | Near-optimal learning of tree-structured distributions by Chow-Liu. Arnab Bhattacharyya, Sutanu Gayen, Eric Price, N. V. Vinodchandran |
| 2021 | Neural tangent kernel: convergence and generalization in neural networks (invited paper). Arthur Jacot, Franck Gabriel, Clément Hongler |
| 2021 | New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√ Tali Kaufman, Ran J. Tessler |
| 2021 | New separations results for external information. Mark Braverman, Dor Minzer |
| 2021 | On codes decoding a constant fraction of errors on the BSC. Jan Hazla, Alex Samorodnitsky, Ori Sberlo |
| 2021 | Online stochastic matching, poisson arrivals, and the natural linear program. Zhiyi Huang, Xinkai Shu |
| 2021 | Optimal error resilience of adaptive message exchange. Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
| 2021 | Optimal inapproximability of satisfiable k-LIN over non-abelian groups. Amey Bhangale, Subhash Khot |
| 2021 | Optimal labelling schemes for adjacency, comparability, and reachability. Marthe Bonamy, Louis Esperet, Carla Groenland, Alex D. Scott |
| 2021 | Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. Zongchen Chen, Kuikui Liu, Eric Vigoda |
| 2021 | Optimal testing of discrete distributions with high probability. Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price |
| 2021 | Outcome indistinguishability. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
| 2021 | Perfectly sampling Vishesh Jain, Ashwin Sah, Mehtaab Sawhney |
| 2021 | Playing unique games on certified small-set expanders. Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer |
| 2021 | Polynomial time deterministic identity testing algorithm for Σ Shir Peleg, Amir Shpilka |
| 2021 | Pseudodeterministic algorithms and the structure of probabilistic time. Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam |
| 2021 | Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
| 2021 | Reducing isotropy and volume to KLS: an He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala |
| 2021 | Revelation gap for pricing from samples. Yiding Feng, Jason D. Hartline, Yingkai Li |
| 2021 | Robust linear regression: optimal rates in polynomial time. Ainesh Bakshi, Adarsh Prasad |
| 2021 | Robust testing of low dimensional functions. Anindya De, Elchanan Mossel, Joe Neeman |
| 2021 | SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang |
| 2021 | STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. Samir Khuller, Virginia Vassilevska Williams |
| 2021 | Sample-efficient proper PAC learning with approximate differential privacy. Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi |
| 2021 | Sample-optimal and efficient learning of tree Ising models. Constantinos Daskalakis, Qinxuan Pan |
| 2021 | Sampling constraint satisfaction solutions in the local lemma regime. Weiming Feng, Kun He, Yitong Yin |
| 2021 | Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and differential privacy. Jonathan Leake, Colin S. McSwiggen, Nisheeth K. Vishnoi |
| 2021 | Separating words and trace reconstruction. Zachary Chase |
| 2021 | Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH). Ray Li |
| 2021 | Settling the complexity of Nash equilibrium in congestion games. Yakov Babichenko, Aviad Rubinstein |
| 2021 | Settling the robust learnability of mixtures of Gaussians. Allen Liu, Ankur Moitra |
| 2021 | Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. Lijie Chen, Roei Tell |
| 2021 | Simplicity creates inequity: implications for fairness, stereotypes, and interpretability (invited paper). Jon M. Kleinberg, Sendhil Mullainathan |
| 2021 | Sparse nonnegative convolution is equivalent to dense nonnegative convolution. Karl Bringmann, Nick Fischer, Vasileios Nakos |
| 2021 | Statistical physics of random CSPs (tutorial). Nike Sun |
| 2021 | Statistical query complexity of manifold estimation. Eddie Aamari, Alexander Knop |
| 2021 | Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. Ján Pich, Rahul Santhanam |
| 2021 | Stronger bounds for weak epsilon-nets in higher dimensions. Natan Rubin |
| 2021 | Stronger calibration lower bounds via sidestepping. Mingda Qiao, Gregory Valiant |
| 2021 | Structure vs. randomness for bilinear maps. Alex Cohen, Guy Moshkovitz |
| 2021 | Subcubic algorithms for Gomory-Hu tree in unweighted graphs. Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2021 | Succinct blind Quantum computation using a random oracle. Jiayu Zhang |
| 2021 | Support of closed walks and second eigenvalue multiplicity of graphs. Theo McKenzie, Peter Michael Reichstein Rasmussen, Nikhil Srivastava |
| 2021 | The communication complexity of multiparty set disjointness under product distributions. Nachum Dershowitz, Rotem Oshman, Tal Roth |
| 2021 | The communication complexity of payment computation. Shahar Dobzinski, Shiri Ron |
| 2021 | The complexity of constrained min-max optimization. Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis |
| 2021 | The complexity of gradient descent: CLS = PPAD ∩ PLS. John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani |
| 2021 | The ghost in the radiation: robust encodings of the black hole interior (invited paper). Isaac H. Kim, Eugene Tang, John Preskill |
| 2021 | The limits of pan privacy and shuffle privacy for learning and estimation. Albert Cheu, Jonathan R. Ullman |
| 2021 | The metric relaxation for Roy Schwartz, Nitzan Tur |
| 2021 | The randomized communication complexity of randomized auctions. Aviad Rubinstein, Junyao Zhao |
| 2021 | Tight conditional lower bounds for approximating diameter in directed graphs. Mina Dalirrooyfard, Nicole Wein |
| 2021 | Towards tight bounds for spectral sparsification of hypergraphs. Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | Tree embeddings for hop-constrained network design. Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic |
| 2021 | Universally-optimal distributed algorithms for known topologies. Bernhard Haeupler, David Wajc, Goran Zuzic |
| 2021 | VC dimension and distribution-free sample-based testing. Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms |
| 2021 | Vertex connectivity in poly-logarithmic max-flows. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2021 | Vertex deletion parameterized by elimination distance and even less. Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk |
| 2021 | When is approximate counting for conjunctive queries tractable? Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
| 2021 | When is memorization of irrelevant training data necessary for high-accuracy learning? Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar |
| 2021 | k-forrelation optimally separates Quantum and classical query complexity. Nikhil Bansal, Makrand Sinha |