STOC 2021 Accepted Papers


  • Discrepancy Minimization via a Self-Balancing Walk, Ryan Alweiss (Princeton University); Yang P. Liu (Stanford University); Mehtaab Sawhney (MIT)

  • The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation, Albert Cheu, Jonathan Ullman (Northeastern University)

  • Statistical Query Complexity of Manifold Estimation, Eddie Aamari (Sorbonne Université, Université de Paris, CNRS); Alexander Knop (UCSD)

  • Optimal Testing of Discrete Distributions with High Probability, Ilias Diakonikolas (UW Madison); Themis Gouleakis (MPI, Germany); Daniel M. Kane (UCSD); John Peebles (Princeton University); Eric Price (UT Austin)

  • Efficiently Learning Halfspaces with Tsybakov Noise, Ilias Diakonikolas (UW Madison); Daniel M. Kane (UCSD); Vasilis Kontonis, Christos Tzamos, Nikos Zarifis (UW Madison)

  • Log-rank and lifting for AND-functions, Alexander Knop, Shachar Lovett, Sam McGuire (UCSD); Weiqiang Yuan (Tsinghua University)

  • Continuous LWE, Joan Bruna, Oded Regev, Min Jae Song (New York University); Yi Tang (University of Michigan)

  • Robust Linear Regression: Optimal Rates in Polynomial Time, Ainesh Bakshi, Adarsh Prasad (Carnegie Mellon University)

  • Bipartite Perfect Matching as a Real Polynomial, Gal Beniamini, Noam Nisan (The Hebrew University of Jerusalem)

  • Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups, Amey Bhangale (University of California, Riverside); Subhash Khot (New York University)

  • Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design, Yufei Ruan (University of Illinois at Urbana-Champaign); Jiaqi Yang (Tsinghua University); Yuan Zhou (University of Illinois at Urbana-Champaign)

  • Fiber Bundle Codes: Breaking the N^{1/2} polylog(N) Barrier for Quantum LDPC Codes, Matthew Hastings, Jeongwan Haah (Microsoft Research); Ryan O'Donnell (Carnegie Mellon University)

  • Optimal Learning of Tree-structured Ising models, Constantinos Daskalakis, Qinxuan Pan (MIT)

  • Structure vs. Randomness for Bilinear Maps, Guy Moshkovitz (City University of New York); Alex Cohen (Yale University)

  • Kronecker Products, Low-Depth Circuits, and Matrix Rigidity, Josh Alman (Harvard)

  • A (Slightly) Improved Approximation Algorithm for Metric TSP, Anna Karlin, Nathan Klein, Shayan Oveis Gharan (University of Washington)

  • Iterated lower bound formulas: a diagonalization-based approach to proof complexity, Rahul Santhanam (University of Oxford); Iddo Tzameret (Royal Holloway, University of London)

  • Local Concentration Inequalities and Tomaszewski's Conjecture, Nathan Keller, Ohad Klein (Bar Ilan University)

  • Perfectly Sampling k\geq (8/3 +o(1))\Delta-Colorings in Graphs, Vishesh Jain (Simons Institute for the Theory of Computing); Ashwin Sah, Mehtaab Sawhney (MIT)

  • Polynomial time deterministic identity testing algorithm for \Sigma^{[3]}\Pi\Sigma\Pi^{[2]} circuits via Edelstein-Kelly type theorem for quadratic polynomials, Shir Peleg (Tel Aviv University); Amir Shpilka (Tel-Aviv University)

  • When is Approximate Counting for Conjunctive Queries Tractable?, Marcelo Arenas, Luis Alberto Croquevielle (PUC & IMFD Chile); Rajesh Jayaram (Carnegie Mellon University); Cristian Riveros (PUC & IMFD Chile)

  • On codes decoding a constant fraction of errors on the BSC, Jan Hązła (EPFL); Alex Samorodnitsky (Hebrew University); Ori Sberlo (Tel-Aviv University)

  • Constant Approximating k-Clique is W[1]-hard, Bingkai Lin (Nanjing University)

  • Classification of the streaming approximability of Boolean CSPs, Chi-Ning Chou (Harvard University); Alexander Golovnev (Georgetown University); Madhu Sudan, Santhoshini Velusamy (Harvard University)

  • Reducing Isotropy and Volume to KLS: An O*(n^3 \psi^2) Volume Algorithm, He Jia, Aditi Laddha (Georgia Tech); Yin Tat Lee (University Washington); Santosh Vempala (Georgia Tech)

  • An Optimal Separation of Randomized and Quantum Query Complexity, Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu (UCLA)

  • Distributed Weighted Min-Cut in Nearly-Optimal Time, Michal Dory (ETH Zurich, Switzerland); Yuval Efron (University of Toronto, Canada); Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology, Sweden)

  • A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique, Krzysztof Nowicki (University of Copenhagen and University of Wrocław)

  • A New Coreset Framework for Clustering, Vincent Cohen-Addad (Google Research, Switzerland); David Saulpic (Sorbonne Université, Paris); Chris Schwiegelshohn (Aarhus University)

  • Flow Time Scheduling with Uncertain Processing Time, Yossi Azar (Tel Aviv University); Stefano Leonardi (University of Rome La Sapienza); Noam Touitou (Tel Aviv University)

  • Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors, Jesper Nederlof (Utrecht University); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)

  • Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time, Julia Chuzhoy (Toyota Technological Institute at Chicago)

  • Improved Dynamic Algorithms for Longest Increasing Subsequence, Tomasz Kociumaka (UC Berkeley); Saeed Seddighin (Toyota Technological Institute at Chicago)

  • Decoding Multivariate Multiplicity Codes on Product Sets, Siddharth Bhandari, Prahladh Harsha (Tata Institute of Fundamental Research); Mrinal Kumar (IIT Bombay); Madhu Sudan (Harvard)

  • Sample-efficient proper PAC learning with approximate differential privacy, Badih Ghazi (Google); Noah Golowich (MIT); Ravi Kumar (Google); Pasin Manurangsi (Google Research)

  • New Cosystolic Expanders from Tensors imply Explicit Quantum LDPC Codes with Ω(nlog⁡kn)\Omega(\sqrt{n}\log^k n)Ω(n ​logkn) Distance, Tali Kaufman (BIU); Ran J. Tessler (Weizmann Institute of Science)

  • Boosting Simple Learners, Noga Alon (Princeton University); Alon Gonen (OrCam); Elad Hazan (Princeton); Shay Moran (Technion)

  • Approximating Nash Social Welfare under Rado Valuations, Jugal Garg (University of Illinois at Urbana-Champaign); Edin Husić, László A. Végh (Department of Mathematics, London School of Economics)

  • Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon, Seth Pettie, Dingyu Wang (University of Michigan)

  • How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games, William Kuszmaul (MIT)

  • Finding large induced sparse subgraphs in C>t​-free graphs in quasipolynomial time, Peter Gartland, Daniel Lokshtanov (University of California at Santa Barbara, USA); Marcin Pilipczuk, Michał Pilipczuk (University of Warsaw, Poland); Paweł Rzążewski (Warsaw University of Technology and University of Warsaw, Poland)

  • Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion, Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (University of Washington); Eric Vigoda (Georgia Institute of Technology)

  • How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design, Maria-Florina Balcan (Carnegie Mellon University); Dan DeBlasio (University of Texas at El Paso); Travis Dick (University of Pennsylvania); Carl Kingsford, Tuomas Sandholm, Ellen Vitercik (Carnegie Mellon University)

  • A New Algorithm for Euclidean Shortest Paths in the Plane, Haitao Wang (Utah State University)

  • Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability, Lijie Chen (Massachusetts Institute of Technology); Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena (Princeton University); Zhao Song (School of Mathematics, IAS); Huacheng Yu (Princeton University)

  • Settling the complexity of Nash equilibrium in congestion games, Yakov Babichenko (Technion, Faulty of Industrial Engineering and Management); Aviad Rubinstein (Stanford)

  • k-Forrelation Optimally Separates Quantum and Classical Query Complexity, Nikhil Bansal (CWI Amsterdam and TU Eindhoven); Makrand Sinha (CWI Amsterdam)

  • Adversarial Laws of Large Numbers and Optimal Regret in Online Classification, Noga Alon (Princeton University and Tel Aviv University); Omri Ben-Eliezer (Harvard University); Yuval Dagan (MIT); Shay Moran (Technion); Moni Naor (Weizmann Institute); Eylon Yogev (Tel Aviv University and Boston University)

  • Efficient and near-optimal algorithms for sampling connected subgraphs, Marco Bressan (University of Milan)

  • Clan Embeddings into Trees, and Low Treewidth Graphs, Arnold Filtser (Columbia University); Hung Le (University of Massachusetts, Amherst)

  • New Separations Results for External Information, Mark Braverman (Princeton University); Dor Minzer (MIT)

  • Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH), Ray Li (Stanford University)

  • Efficient List-Decoding with Constant Alphabet and List Sizess, Zeyu Guo, Noga Ron-Zewi (University of Haifa)

  • Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem, Scott Aaronson (University of Texas at Austin); Shalev Ben-David (University of Waterloo); Robin Kothari (Microsoft Quantum and Microsoft Research); Shravas Rao (Northwestern University); Avishay Tal (UC Berkeley)

  • Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity, Jad Silbak (Tel Aviv University); Ronen Shaltiel (University of Haifa)

  • Expander Random Walks: A Fourier-Analytic Approach, Gil Cohen, Noam Peri, Amnon Ta-Shma (Tel Aviv University)

  • Stronger Calibration Lower Bounds via Sidestepping, Mingda Qiao, Gregory Valiant (Stanford University)

  • Eliminating Intermediate Measurements in Space-Bounded Quantum Computation, Bill Fefferman, Zachary Remscrim (The University of Chicago)

  • The Complexity of Gradient Descent: CLS = PPAD ∩\cap∩ PLS, John Fearnley (University of Liverpool); Paul W. Goldberg, Alexandros Hollender (University of Oxford); Rahul Savani (University of Liverpool)

  • Tree Embeddings for Hop-Constrained Network Design, Bernhard Haeupler, D Ellis Hershkowitz (Carnegie Mellon University); Goran Zuzic (ETH Zurich)

  • An Improved Derandomization of the Switching Lemma, Zander Kelley (University of Illinois at Urbana-Champaign)

  • SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE, Ruta Jawale (University of Illinois at Urbana-Champaign); Yael Tauman Kalai (Microsoft Research, Massachusetts Institute of Technology); Dakshita Khurana (University of Illinois at Urbana-Champaign); Rachel Zhang (Massachusetts Institute of Technology)

  • 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 (University of Washington)

  • Revelation Gap for Pricing from Samples, Yiding Feng, Jason Hartline, Yingkai Li (Northwestern University)

  • A Faster Algorithm for Solving General LPs, Shunhua Jiang (Columbia University); Zhao Song (School of Mathematics, IAS); Omri Weinstein, Hengjie Zhang (Columbia University)

  • Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost, Lijie Chen, Roei Tell (Massachusetts Institute of Technology)

  • Towards Tight Bounds for Spectral Sparsification of Hypergraphs, Michael Kapralov (EPFL); Robert Krauthgamer (Weizmann Institute of Science); Jakab Tardos (EPFL); Yuichi Yoshida (National Institute of Informatics)

  • Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions, Natan Rubin (Ben-Gurion University)

  • Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces, Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University)

  • Outcome Indistinguishability, Cynthia Dwork (Harvard University); Michael P. Kim (UC Berkeley); Omer Reingold (Stanford University); Guy N. Rothblum, Gal Yona (Weizmann Institute of Science)

  • Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions, Shuichi Hirahara (National Institute of Informatics)

  • Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu, Arnab Bhattacharyya, Sutanu Gayen (National University of Singapore); Eric Price (The University of Texas at Austin); N. V. Vinodchandran (University of Nebraska-Lincoln)

  • Hardness of Learning DNFs using Halfspaces, Suprovat Ghoshal (Indian Institute of Science); Rishi Saket (IBM Research)

  • Vertex Deletion Parameterized by Elimination Distance and Even Less, Bart M. P. Jansen, Jari J. H. de Kroon, Michał Włodarczyk (Eindhoven University of Technology)

  • Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity, Arkadev Chattopadhyay (Tata Institue of Fundamental Research); Rajit Datta, Partha Mukhopadhyay (Chennai Mathematical Institute)

  • Indistinguishability Obfuscation from Circular Security, Romain Gay (IBM Research Zurich); Rafael Pass (Cornell Tech)

  • The Metric Relaxation for 000-Extension Admits an \Omega(\log^{\nicefrac[]{2}{3}}{k}) Gap, Roy Schwartz, Nitzan Tur (Technion)

  • Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes, Rad Niazadeh (University of Chicago Booth School of Business); Renato Paes Leme, Jon Schneider (Google Research)

  • Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs, Amir Abboud (IBM Almaden Research Center); Robert Krauthgamer, Ohad Trabelsi (Weizmann Institute of Science)

  • Learning Ising models from one or multiple samples, Yuval Dagan, Anthimos-Vardis Kandiros (MIT); Constantinos Daskalakis (EECS, MIT); Nishanth Dikkala (Google)

  • A (2 + \epsilon)-approximation algorithm for preemptive weighted flow time on a single machine, Lars Rohwedder (EPFL); Andreas Wiese (Universidad de Chile)

  • Efficient Two-Sided Markets with Limited Information, Paul Duetting (Google Research); Federico Fusco, Philip Lazos (Sapienza University of Rome); Stefano Leonardi (University of Rome La Sapienza); Rebecca Reiffenhauser (Sapienza University of Rome)

  • Optimal Error Resilience of Adaptive Message Exchange, Klim Efremenko (Ben-Gurion University); Gillat Kol, Raghuvansh Saxena (Princeton University)

  • Algorithmic Foundations for the Diffraction Limit, Sitan Chen, Ankur Moitra (MIT)

  • Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program, Zhiyi Huang, Xinkai Shu (The University of Hong Kong)

  • Automating Algebraic Proof Systems is NP-Hard, Susanna F. de Rezende (Institute of Mathematics of the Czech Academy of Sciences); Mika Göös (EPFL); Jakob Nordström (University of Copenhagen & Lund University); Toniann Pitassi (University of Toronto & IAS); Robert Robere (McGill University); Dmitry Sokolov (St. Petersburg State University & PDMI RAS)

  • Universally-Optimal Distributed Algorithms for Known Topologies, Bernhard Haeupler (Carnegie Mellon University); David Wajc (Stanford University); Goran Zuzic (ETH Zurich)

  • Succinct Blind Quantum Computation Using a Random Oracle, Jiayu Zhang (Boston University)

  • The Communication Complexity of Payment Computation, Shahar Dobzinski, Shiri Ron (Weizmann Institute of Science)

  • Settling the Robust Learnability of Mixtures of Gaussians, Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT)

  • Pseudodeterministic Algorithms and the Structure of Probabilistic Time, Zhenjian Lu, Igor C. Oliveira (University of Warwick); Rahul Santhanam (University of Oxford)

  • Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches, Federica Cecchetto, Vera Traub, Rico Zenklusen (ETH Zurich)

  • A Theory of Universal Learning, Olivier Bousquet (Google, Brain Team); Steve Hanneke (TTIC); Shay Moran (Technion); Ramon van Handel (Princeton University); Amir Yehudayoff (Technion)

  • Vertex Connectivity in Poly-logarithmic Max-flows, Jason Li (Carnegie Mellon University); Danupon Nanongkai (KTH Royal Institute of Technology); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (Toyota Technological Institute at Chicago); Sorrachai Yingchareonthawornchai (Aalto University)

  • Efficient Randomized Distributed Coloring in CONGEST, Magnus M. Halldorsson (Reykjavik University); Fabian Kuhn (University of Freiburg); Yannic Maus, Tigran Tonoyan (Technion - Israel Institute of Technology)

  • Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution, Karl Bringmann, Nick Fischer, Vasileios Nakos (Saarland University and Max Planck Institute for Informatics)

  • Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests, Nima Anari (Stanford University); Kuikui Liu, Shayan Oveis Gharan (University of Washington); Cynthia Vinzant (North Carolina State University); Thuy-Duong Vuong (Stanford University)

  • Breaking the Quadratic Barrier for Matroid Intersection, Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology)

  • Indistinguishability Obfuscation from Well-Founded Assumptions, Aayush Jain (UCLA); Huijia Lin (University of Washington); Amit Sahai (UCLA)

  • Sampling Matrices from Harish-Chandra--Itzykson–Zuber Densities with Applications to Quantum Inference and Differential Privacy, Jonathan Leake (TU Berlin); Colin McSwiggen (Brown University); Nisheeth K. Vishnoi (Yale University)

  • Entropy decay in the Swendsen-Wang dynamics on Z^d, Antonio Blanca (Penn State); Pietro Caputo, Daniel Parisi (University of Roma Tre); Alistair Sinclair (U.C. Berkeley); Eric Vigoda (Georgia Tech)

  • Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits, Vishwas Bhargava, Shubhangi Saraf (Rutgers University); Ilya Volkovich (Boston College)

  • Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization, Oren Mangoubi (WPI); Nisheeth K. Vishnoi (Yale University)

  • Hop-Constrained Oblivious Routing, Mohsen Ghaffari (ETH Zurich); Bernhard Haeupler (Carnegie Mellon University); Goran Zuzic (ETH Zurich)

  • Playing Unique Games on Certified Small-Set Expanders, Mitali Bafna, Boaz Barak (Harvard); Pravesh Kothari (CMU); Tselil Schramm (Stanford); David Steurer (ETH Zurich)

  • Dynamic Planar Point Location in Optimal Time, Yakov Nekrich (Michigan Technological University)

  • Sampling Constraint Satisfaction Solutions in the Local Lemma Regime, Weiming Feng (Nanjing University); Kun He (ICT,CAS); Yitong Yin (Nanjing University)

  • (Sub)Exponential advantage of adiabatic quantum computation with no sign problem, András Gilyén (IQIM, Caltech); Matthew Hastings (Microsoft Research); Umesh Vazirani (U.C. Berkeley)

  • Optimal labelling schemes for adjacency, comparability and reachability, Marthe Bonamy (CNRS, Labri, Université de Bordeaux); Louis Esperet (CNRS, G-SCOP, Univ. Grenoble Alpes); Carla Groenland, Alex Scott (University of Oxford)

  • A Quasipolynomial (2 + ε)-Approximation for Planar Sparsest Cut, Vincent Cohen-Addad (Google Research, Switzerland); Anupam Gupta (Carnegie Mellon); Philip N Klein (Brown University); Jason Li (Carnegie Mellon University)

  • VC Dimension and Distribution-Free Sample-Based Testing, Eric Blais, Renato Ferreira Pinto, Jr., Nathaniel Harms (University of Waterloo)

  • Capacity Lower Bounds via Productization, Leonid Gurvits (The City College of New York); Jonathan Leake (TU Berlin)

  • The Communication Complexity of Multiparty Set Disjointness Under Product Distributions, Nachum Dershowitz, Rotem Oshman, Tal Roth (Tel Aviv University)

  • Load balancing with Dynamic Set of Balls and Bin, Anders Aamand, Mikkel Thorup, Jakob Knudsen (University of Copenhagen)

  • Minimum Cost Flows, MDPs, and \ell_1​-Regression in Nearly Linear Time for Dense Instances, Jan van den Brand (KTH Royal Institute of Technology); Yin Tat Lee (University Washington); Yang P. Liu (Stanford University); Thatchaphol Saranurak (Toyota Technological Institute at Chicago); Aaron Sidford (Stanford University); Zhao Song (School of Mathematics, IAS); Di Wang (Google)

  • Improved quantum data analysis, Costin Bădescu, Ryan O'Donnell (Carnegie Mellon University)

  • Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma, Sepehr Assadi, Vishvajeet Nagargoje (Rutgers University)

  • The randomized communication complexity of optimal randomized auctions, Aviad Rubinstein; Junyao Zhao (Stanford University)

  • Approximate Gomory-Hu Tree Is Faster than n−1 Max-flows, Jason Li (Carnegie Mellon University); Debmalya Panigrahi (Duke University)

  • A Framework for Dynamic Matching in Weighted Graphs, Zachary Langley, Aditi Dudeja, Aaron Bernstein (Rutgers University)

  • Deterministic Mincut in Almost-Linear Time, Jason Li (Carnegie Mellon University)

  • Robust testing of low dimensional functions, Anindya De (University of Pennsylvania); Elchanan Mossel (MIT); Joe Neeman (University of Texas, Austin)

  • Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge), Justin Holmgren (NTT Research); Alex Lombardi (MIT); Ron Rothblum (Technion)

  • Strong Co-Nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly, Jan Pich, Rahul Santhanam (University of Oxford)

  • Separating Words and Trace Reconstruction, Zachary Chase (University of Oxford)

  • Frozen 1-RSB structure of the symmetric Ising perceptron, Will Perkins (University of Illinois Chicago); Changji Xu (Harvard University)

  • Contextual search in the presence of irrational agents, Akshay Krishnamurthy, Thodoris Lykouris (Microsoft Research NYC); Chara Podimata (Harvard University); Robert Schapire (Microsoft Research NYC)

  • Cryptography from Sublinear-Time Hardness of Time-Bounded Kolmogorov Complexity, Yanyi Liu, Rafael Pass (Cornell University)

  • Fully Dynamic Approximation of LIS in Polylogarithmic Time, Pawel Gawrychowski, Wojciech Janczewski (University of Wrocław)

  • Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More, Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong (Stanford University)

  • A full complexity dichotomy for immanant families, Radu Curticapean (IT University of Copenhagen, Basic Algorithms Research Copenhagen)

  • The Complexity of Constrained Min-Max Optimization, Constantinos Daskalakis (EECS, MIT); Stratis Skoulakis (ESD, SUTD); Manolis Zampetakis (UC Berkeley)

  • Near-linear Time Decoding of Ta-Shma's Codes via Splittable Regularity, Fernando Granha Jeronimo (University of Chicago); Shashank Srivastava, Madhur Tulsiani (TTIC)

  • Exponential Communication Separations between Notions of Selfishness, Aviad Rubinstein (Stanford University); Raghuvansh Saxena, Clayton Thomas, S. Matthew Weinberg (Princeton University); Junyao Zhao (Stanford University)

  • A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations, Vijay Bhattiprolu (IAS/Princeton); Euiwoong Lee (University of Michigan); Assaf Naor (Princeton University)

  • Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs, Theo McKenzie (University of California, Berkeley); Peter M. R. Rasmussen (University of Copenhagen); Nikhil Srivastava (UC Berkeley)

  • Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs, Mina Dalirrooyfard, Nicole Wein (MIT)

  • When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?, Gavin Brown, Mark Bun (Boston University); Vitaly Feldman (Apple); Adam Smith (Boston University); Kunal Talwar (Apple)

  • Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma, Lijie Chen (Massachusetts Institute of Technology); Xin Lyu (Tsinghua University)

  • Efficient Randomized DCAS, George Giakkoupis (INRIA, Rennes); Mehrdad Jafari Giv, Philipp Woelfel (University of Calgary)