STOC 2021 Accepted Papers
 Discrepancy Minimization via a SelfBalancing 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)

Logrank and lifting for ANDfunctions, 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 kLIN over NonAbelian 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 UrbanaChampaign); Jiaqi Yang (Tsinghua University); Yuan Zhou (University of Illinois at UrbanaChampaign)

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 Treestructured 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, LowDepth 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 diagonalizationbased 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))\DeltaColorings 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 EdelsteinKelly type theorem for quadratic polynomials,
Shir Peleg (Tel Aviv University); Amir Shpilka (TelAviv 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 (TelAviv University)

Constant Approximating kClique is W[1]hard, Bingkai Lin (Nanjing University)

Classification of the streaming approximability of Boolean CSPs, ChiNing 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 MinCut in NearlyOptimal 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 CohenAddad (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 AllPairs Shortest Paths in Deterministic NearLinear 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)

Sampleefficient 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 Ω(nlogkn)\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 UrbanaChampaign); 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>tfree 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 HighDimensional 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 highperforming algorithms? Generalization guarantees for datadriven algorithm design, MariaFlorina 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 SuperConstantPass 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)

kForrelation 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 BenEliezer (Harvard University); Yuval Dagan (MIT); Shay Moran (Technion); Moni Naor (Weizmann Institute); Eylon Yogev (Tel Aviv University and Boston University)

Efficient and nearoptimal 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 ListDecoding with Constant Alphabet and List Sizess, Zeyu Guo, Noga RonZewi (University of Haifa)

Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem, Scott Aaronson (University of Texas at Austin); Shalev BenDavid (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 ListDecoding Capacity, Jad Silbak (Tel Aviv University); Ronen Shaltiel (University of Haifa)

Expander Random Walks: A FourierAnalytic Approach, Gil Cohen, Noam Peri, Amnon TaShma (Tel Aviv University)

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

Eliminating Intermediate Measurements in SpaceBounded 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 HopConstrained 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 UrbanaChampaign)

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

A NearlyLinear 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 EpsilonNets in Higher Dimensions, Natan Rubin (BenGurion University)

Nearlinear time approximation schemes for Steiner tree and forest in lowdimensional spaces, Yair Bartal (Hebrew University); LeeAd 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)

AverageCase Hardness of NP from Exponential WorstCase Hardness Assumptions, Shuichi Hirahara (National Institute of Informatics)

NearOptimal Learning of TreeStructured Distributions by ChowLiu, Arnab Bhattacharyya, Sutanu Gayen (National University of Singapore); Eric Price (The University of Texas at Austin); N. V. Vinodchandran (University of NebraskaLincoln)

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 000Extension 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 GomoryHu 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, AnthimosVardis 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 TwoSided 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 (BenGurion 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 NPHard, 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)

UniversallyOptimal 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 Polylogarithmic Maxflows, 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)

LogConcave Polynomials IV: Approximate Exchange, Tight Mixing Times, and NearOptimal Sampling of Forests, Nima Anari (Stanford University); Kuikui Liu, Shayan Oveis Gharan (University of Washington); Cynthia Vinzant (North Carolina State University); ThuyDuong 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 WellFounded Assumptions, Aayush Jain (UCLA); Huijia Lin (University of Washington); Amit Sahai (UCLA)

Sampling Matrices from HarishChandraItzykson–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 SwendsenWang 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 LowRank Tensors and Depth3 Multilinear Circuits, Vishwas Bhargava, Shubhangi Saraf (Rutgers University); Ilya Volkovich (Boston College)

Greedy Adversarial Equilibrium: An Efficient Alternative to NonconvexNonconcave MinMax Optimization, Oren Mangoubi (WPI); Nisheeth K. Vishnoi (Yale University)

HopConstrained Oblivious Routing, Mohsen Ghaffari (ETH Zurich); Bernhard Haeupler (Carnegie Mellon University); Goran Zuzic (ETH Zurich)

Playing Unique Games on Certified SmallSet 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, GSCOP, Univ. Grenoble Alpes); Carla Groenland, Alex Scott (University of Oxford)

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

VC Dimension and DistributionFree SampleBased 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_1Regression 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 GomoryHu Tree Is Faster than n−1 Maxflows, 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 AlmostLinear 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)

FiatShamir via ListRecoverable Codes (or: Parallel Repetition of GMW is not ZeroKnowledge), Justin Holmgren (NTT Research); Alex Lombardi (MIT); Ron Rothblum (Technion)

Strong CoNondeterministic 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 1RSB 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 SublinearTime Hardness of TimeBounded 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 LogConcave and SectorStable Polynomials: Counting Planar Matchings and More, Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, ThuyDuong Vuong (Stanford University)

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

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

Nearlinear Time Decoding of TaShma'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 HighAccuracy Learning?, Gavin Brown, Mark Bun (Boston University); Vitaly Feldman (Apple); Adam Smith (Boston University); Kunal Talwar (Apple)

InverseExponential 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)