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 (Imperial College 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 N (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)