STOC 2021 – Proceedings

Frontmatter

Invited Presentations

Keynote

Computational Thinking in Programming Language and Compiler Design (Keynote)
Alfred V. Aho
(Columbia University, USA)

Publisher's Version Article: stoc21invited-inv2-p (type: Abstract (1 page)) doi:10.1145/3406325.3465350

Invited Talk

Climbing Algorithms (Invited Talk)
Leonid A. Levin
(Boston University, USA)

Publisher's Version Article: stoc21invited-inv1-p (type: Extended Abstract (4 pages)) doi:10.1145/3406325.3457137

Invited Papers

A Polynomial-Time Approximation Algorithm for Counting Words Accepted by an NFA (Invited Paper)
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros
(PUC, Chile; IMFD, Chile; Carnegie Mellon University, USA)

Publisher's Version Article: stoc21invited-inv5-p (type: Abstract (1 page)) doi:10.1145/3406325.3465353

Chasing Convex Bodies with Linear Competitive Ratio (Invited Paper)
C. J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang
(Carnegie Mellon University, USA; Google Research, USA)

Publisher's Version Article: stoc21invited-inv6-p (type: Abstract (1 page)) doi:10.1145/3406325.3465354

Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Invited Paper)
Arthur Jacot, Franck Gabriel, and Clément Hongler
(EPFL, Switzerland)

Publisher's Version Article: stoc21invited-inv7-p (type: Abstract (1 page)) doi:10.1145/3406325.3465355

Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability (Invited Paper)
Jon Kleinberg and Sendhil Mullainathan
(Cornell University, USA; University of Chicago, USA)

Publisher's Version Article: stoc21invited-inv8-p (type: Abstract (1 page)) doi:10.1145/3406325.3465356

The Ghost in the Radiation: Robust Encodings of the Black Hole Interior (Invited Paper)
Isaac H. Kim, Eugene Tang, and John Preskill
(University of Sydney, Australia; California Institute of Technology, USA)

Publisher's Version Article: stoc21invited-inv9-p (type: Abstract (1 page)) doi:10.1145/3406325.3465357

A New Analysis of Differential Privacy’s Generalization Guarantees (Invited Paper)
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld
(University of Pennsylvania, USA; Hebrew University of Jerusalem, Israel)

Publisher's Version Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358

Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times (Invited Paper)
Isaac Grosof, Ziv Scully, and Mor Harchol-Balter
(Carnegie Mellon University, USA)

Publisher's Version Article: stoc21invited-inv11-p (type: Abstract (1 page)) doi:10.1145/3406325.3465359

Learnability Can Be Independent of Set Theory (Invited Paper)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff
(University of Waterloo, Canada; Czech Academy of Sciences, Czechia; Technion, Israel; Tel Aviv University, Israel)

Publisher's Version Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360

Tutorials

Log-Concave Polynomials in Theory and Applications (Tutorial)
Nima Anari and Cynthia Vinzant
(Stanford University, USA; North Carolina State University, USA; University of Washington, USA)

Publisher's Version Article: stoc21invited-inv3-p (type: Abstract (1 page)) doi:10.1145/3406325.3465351

Statistical Physics of Random CSPs (Tutorial)
Nike Sun
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21invited-inv4-p (type: Abstract (1 page)) doi:10.1145/3406325.3465352

Papers

Best Student Papers

Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney
(Princeton University, USA; Stanford University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p2-p (type: Full Paper) doi:10.1145/3406325.3450994

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

Publisher's Version Article: stoc21main-p443-p (type: Full Paper) doi:10.1145/3406325.3451118

Best Papers

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

Publisher's Version Article: stoc21main-p49-p (type: Full Paper) doi:10.1145/3406325.3451009

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

Publisher's Version Article: stoc21main-p173-p (type: Full Paper) doi:10.1145/3406325.3451052

Indistinguishability Obfuscation from Well-Founded Assumptions
Aayush Jain, Huijia Lin, and Amit Sahai
(University of California at Los Angeles, USA; University of Washington, USA)

Publisher's Version Article: stoc21main-p329-p (type: Full Paper) doi:10.1145/3406325.3451093

Session 1A

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

Publisher's Version Article: stoc21main-p31-p (type: Full Paper) doi:10.1145/3406325.3451004

Efficiently Learning Halfspaces with Tsybakov Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis
(University of Wisconsin-Madison, USA; University of California at San Diego, USA)

Publisher's Version Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998

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

Publisher's Version Article: stoc21main-p26-p (type: Full Paper) doi:10.1145/3406325.3451001

Statistical Query Complexity of Manifold Estimation
Eddie Aamari and Alexander Knop
(LPSM, France; Sorbonne University, France; University of Paris, France; CNRS, France; University of California at San Diego, USA)

Publisher's Version Article: stoc21main-p11-p (type: Full Paper) doi:10.1145/3406325.3451135

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

Publisher's Version Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131

Session 2A

Sample-Optimal and Efficient Learning of Tree Ising Models
Constantinos Daskalakis and Qinxuan Pan
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p39-p (type: Full Paper) doi:10.1145/3406325.3451006

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

Publisher's Version Article: stoc21main-p217-p (type: Full Paper) doi:10.1145/3406325.3451066

Learning Ising Models from One or Multiple Samples
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros
(Massachusetts Institute of Technology, USA; Google, USA)

Publisher's Version Article: stoc21main-p266-p (type: Full Paper) doi:10.1145/3406325.3451074

A New Coreset Framework for Clustering
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn
(Google, Switzerland; Sorbonne University, France; CNRS, France; LIP6, France; Aarhus University, Denmark)

Publisher's Version Article: stoc21main-p81-p (type: Full Paper) doi:10.1145/3406325.3451022

Sample-Efficient Proper PAC Learning with Approximate Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi
(Google Research, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p98-p (type: Full Paper) doi:10.1145/3406325.3451028

Session 1B

Log-Rank and Lifting for AND-Functions
Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan
(University of California at San Diego, USA; Tsinghua University, China)

Publisher's Version Article: stoc21main-p21-p (type: Full Paper) doi:10.1145/3406325.3450999

Automating Algebraic Proof Systems Is NP-Hard
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, and Dmitry Sokolov
(Czech Academy of Sciences, Czechia; EPFL, Switzerland; University of Copenhagen, Denmark; Lund University, Sweden; University of Toronto, Canada; Institute for Advanced Study at Princeton, USA; McGill University, Canada; St. Petersburg State University, Russia; Russian Academy of Sciences, Russia)

Publisher's Version Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080

Strong Co-nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly
Ján Pich and Rahul Santhanam
(Czech Academy of Sciences, Czechia; University of Oxford, UK)

Publisher's Version Article: stoc21main-p436-p (type: Full Paper) doi:10.1145/3406325.3451117

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
Rahul Santhanam and Iddo Tzameret
(University of Oxford, UK; Imperial College London, UK)

Publisher's Version Article: stoc21main-p50-p (type: Full Paper) doi:10.1145/3406325.3451010

New Separations Results for External Information
Mark Braverman and Dor Minzer
(Princeton University, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p154-p (type: Full Paper) doi:10.1145/3406325.3451044

Session 2B

Polynomial Time Deterministic Identity Testing Algorithm for Σ^[3]ΠΣΠ^[2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials
Shir Peleg and Amir Shpilka
(Tel Aviv University, Israel)

Publisher's Version Article: stoc21main-p57-p (type: Full Paper) doi:10.1145/3406325.3451013

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

Publisher's Version Article: stoc21main-p176-p (type: Full Paper) doi:10.1145/3406325.3451054

Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost
Lijie Chen and Roei Tell
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p192-p (type: Full Paper) doi:10.1145/3406325.3451059

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

Publisher's Version Article: stoc21main-p215-p (type: Full Paper) doi:10.1145/3406325.3451065

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

Publisher's Version Article: stoc21main-p306-p (type: Full Paper) doi:10.1145/3406325.3451085

Session 1C

Vertex Connectivity in Poly-logarithmic Max-Flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai
(Carnegie Mellon University, USA; University of Copenhagen, Denmark; KTH, Sweden; Duke University, USA; University of Michigan, USA; Aalto University, Finland)

Publisher's Version Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088

Finding Large Induced Sparse Subgraphs in C_>t -Free Graphs in Quasipolynomial Time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski
(University of California at Santa Barbara, USA; University of Warsaw, Poland; Warsaw University of Technology, Poland)

Publisher's Version Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034

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

Publisher's Version Article: stoc21main-p148-p (type: Full Paper) doi:10.1145/3406325.3451043

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

Publisher's Version Article: stoc21main-p175-p (type: Full Paper) doi:10.1145/3406325.3451053

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

Publisher's Version Article: stoc21main-p308-p (type: Full Paper) doi:10.1145/3406325.3451086

Session 2C

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

Publisher's Version Article: stoc21main-p420-p (type: Full Paper) doi:10.1145/3406325.3451114

Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs
Theo McKenzie, Peter Michael Reichstein Rasmussen, and Nikhil Srivastava
(University of California at Berkeley, USA; University of Copenhagen, Denmark)

Publisher's Version Article: stoc21main-p488-p (type: Full Paper) doi:10.1145/3406325.3451129

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

Publisher's Version Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091

Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai
(KTH, Sweden; University of Copenhagen, Denmark)

Publisher's Version Article: stoc21main-p325-p (type: Full Paper) doi:10.1145/3406325.3451092

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

Publisher's Version Article: stoc21main-p456-p (type: Full Paper) doi:10.1145/3406325.3451123

Session 3A

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

Publisher's Version Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041

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

Publisher's Version Article: stoc21main-p170-p (type: Full Paper) doi:10.1145/3406325.3451050

Hardness of Learning DNFs using Halfspaces
Suprovat Ghoshal and Rishi Saket
(University of Michigan, USA; IBM Research, India)

Publisher's Version Article: stoc21main-p228-p (type: Full Paper) doi:10.1145/3406325.3451067

Boosting Simple Learners
Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
(Princeton University, USA; Tel Aviv University, Israel; OrCam, Israel; Google AI, USA; Technion, Israel; Google Research, Israel)

Publisher's Version Article: stoc21main-p105-p (type: Full Paper) doi:10.1145/3406325.3451030

Algorithmic Foundations for the Diffraction Limit
Sitan Chen and Ankur Moitra
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p276-p (type: Full Paper) doi:10.1145/3406325.3451078

Session 4A

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

Publisher's Version Article: stoc21main-p380-p (type: Full Paper) doi:10.1145/3406325.3451104

Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu and Ankur Moitra
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p304-p (type: Full Paper) doi:10.1145/3406325.3451084

A Theory of Universal Learning
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff
(Google, Switzerland; Toyota Technological Institute at Chicago, USA; Technion, Israel; Google Research, Israel; Princeton University, USA)

Publisher's Version Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087

Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price
(University of Wisconsin-Madison, USA; MPI-INF, Germany; University of California at San Diego, USA; Princeton University, USA; University of Texas at Austin, USA)

Publisher's Version Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997

Session 3B

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

Publisher's Version Article: stoc21main-p114-p (type: Full Paper) doi:10.1145/3406325.3451032

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu
(Massachusetts Institute of Technology, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038

Robust Testing of Low Dimensional Functions
Anindya De, Elchanan Mossel, and Joe Neeman
(University of Pennsylvania, USA; Massachusetts Institute of Technology, USA; University of Texas at Austin, USA)

Publisher's Version Article: stoc21main-p421-p (type: Full Paper) doi:10.1145/3406325.3451115

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

Publisher's Version Article: stoc21main-p205-p (type: Full Paper) doi:10.1145/3406325.3451061

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

Publisher's Version Article: stoc21main-p408-p (type: Full Paper) doi:10.1145/3406325.3451110

Session 4B

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

Publisher's Version Article: stoc21main-p94-p (type: Full Paper) doi:10.1145/3406325.3451025

Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka and Saeed Seddighin
(University of California at Berkeley, USA; Toyota Technological Institute at Chicago, USA)

Publisher's Version Article: stoc21main-p95-p (type: Full Paper) doi:10.1145/3406325.3451026

Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski and Wojciech Janczewski
(University of Wrocław, Poland)

Publisher's Version Article: stoc21main-p455-p (type: Full Paper) doi:10.1145/3406325.3451137

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

Publisher's Version Article: stoc21main-p418-p (type: Full Paper) doi:10.1145/3406325.3451113

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

Publisher's Version Article: stoc21main-p277-p (type: Full Paper) doi:10.1145/3406325.3451079

Session 3C

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

Publisher's Version Article: stoc21main-p24-p (type: Full Paper) doi:10.1145/3406325.3451000

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

Publisher's Version Article: stoc21main-p180-p (type: Full Paper) doi:10.1145/3406325.3451055

Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
Yanyi Liu and Rafael Pass
(Cornell University, USA)

Publisher's Version Article: stoc21main-p452-p (type: Full Paper) doi:10.1145/3406325.3451121

Indistinguishability Obfuscation from Circular Security
Romain Gay and Rafael Pass
(IBM Research, Switzerland; Cornell Tech, USA)

Publisher's Version Article: stoc21main-p242-p (type: Full Paper) doi:10.1145/3406325.3451070

Fiat–Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge)
Justin Holmgren, Alex Lombardi, and Ron D. Rothblum
(NTT Research, USA; Massachusetts Institute of Technology, USA; Technion, Israel)

Publisher's Version Article: stoc21main-p422-p (type: Full Paper) doi:10.1145/3406325.3451116

Session 4C

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

Publisher's Version Article: stoc21main-p491-p (type: Full Paper) doi:10.1145/3406325.3451132

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

Publisher's Version Article: stoc21main-p43-p (type: Full Paper) doi:10.1145/3406325.3451008

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

Publisher's Version Article: stoc21main-p241-p (type: Full Paper) doi:10.1145/3406325.3451069

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

Publisher's Version Article: stoc21main-p41-p (type: Full Paper) doi:10.1145/3406325.3451007

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

Publisher's Version Article: stoc21main-p336-p (type: Full Paper) doi:10.1145/3406325.3451096

Session 5A

A Faster Algorithm for Solving General LPs
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang
(Columbia University, USA; Institute for Advanced Study at Princeton, USA)

Publisher's Version Article: stoc21main-p191-p (type: Full Paper) doi:10.1145/3406325.3451058

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

Publisher's Version Article: stoc21main-p250-p (type: Full Paper) doi:10.1145/3406325.3451072

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

Publisher's Version Article: stoc21main-p381-p (type: Full Paper) doi:10.1145/3406325.3451105

Minimum Cost Flows, MDPs, and ℓ₁-Regression in Nearly Linear Time for Dense Instances
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang
(KTH, Sweden; University of Washington, USA; Microsoft Research, USA; Stanford University, USA; University of Michigan, USA; Princeton University, USA; Institute for Advanced Study at Princeton, USA; Google Research, USA)

Publisher's Version Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108

A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations
Vijay Bhattiprolu, Euiwoong Lee, and Assaf Naor
(Institute for Advanced Study at Princeton, USA; Princeton University, USA; University of Michigan, USA)

Publisher's Version Article: stoc21main-p483-p (type: Full Paper) doi:10.1145/3406325.3451128

Session 5B

The Randomized Communication Complexity of Randomized Auctions
Aviad Rubinstein and Junyao Zhao
(Stanford University, USA)

Publisher's Version Article: stoc21main-p414-p (type: Full Paper) doi:10.1145/3406325.3451111

Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization
Oren Mangoubi and Nisheeth K. Vishnoi
(Worcester Polytechnic Institute, USA; Yale University, USA)

Publisher's Version Article: stoc21main-p340-p (type: Full Paper) doi:10.1145/3406325.3451097

Contextual Search in the Presence of Irrational Agents
Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire
(Microsoft Research, USA; Harvard University, USA)

Publisher's Version Article: stoc21main-p449-p (type: Full Paper) doi:10.1145/3406325.3451120

How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik
(Carnegie Mellon University, USA; University of Texas at El Paso, USA; University of Pennsylvania, USA)

Publisher's Version Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036

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

Publisher's Version Article: stoc21main-p303-p (type: Full Paper) doi:10.1145/3406325.3451083

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

Publisher's Version Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127

Session 5C

Reducing Isotropy and Volume to KLS: An O*(n³ψ²) Volume Algorithm
He Jia, Aditi Laddha, Yin Tat Lee, and Santosh Vempala
(Georgia Institute of Technology, USA; University of Washington, USA; Microsoft Research, USA)

Publisher's Version Article: stoc21main-p73-p (type: Full Paper) doi:10.1145/3406325.3451018

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

Publisher's Version Article: stoc21main-p128-p (type: Full Paper) doi:10.1145/3406325.3451037

Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
Natan Rubin
(Ben-Gurion University of the Negev, Israel)

Publisher's Version Article: stoc21main-p209-p (type: Full Paper) doi:10.1145/3406325.3451062

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

Publisher's Version Article: stoc21main-p368-p (type: Full Paper) doi:10.1145/3406325.3451100

Session 6A

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

Publisher's Version Article: stoc21main-p60-p (type: Full Paper) doi:10.1145/3406325.3451014

Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces
Yair Bartal and Lee-Ad Gottlieb
(Hebrew University of Jerusalem, Israel; Ariel University, Israel)

Publisher's Version Article: stoc21main-p210-p (type: Full Paper) doi:10.1145/3406325.3451063

A (2 + ε)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Lars Rohwedder and Andreas Wiese
(EPFL, Switzerland; University of Chile, Chile)

Publisher's Version Article: stoc21main-p269-p (type: Full Paper) doi:10.1145/3406325.3451075

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

Publisher's Version Article: stoc21main-p379-p (type: Full Paper) doi:10.1145/3406325.3451103

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

Publisher's Version Article: stoc21main-p83-p (type: Full Paper) doi:10.1145/3406325.3451023

Session 7A

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

Publisher's Version Article: stoc21main-p3-p (type: Full Paper) doi:10.1145/3406325.3450995

Outcome Indistinguishability
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona
(Harvard University, USA; University of California at Berkeley, USA; Stanford University, USA; Weizmann Institute of Science, Israel)

Publisher's Version Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064

Optimal Labelling Schemes for Adjacency, Comparability, and Reachability
Marthe Bonamy, Louis Esperet, Carla Groenland, and Alex Scott
(CNRS, France; Labri, France; University of Bordeaux, France; G-SCOP, France; Grenoble Alps University, France; University of Oxford, UK)

Publisher's Version Article: stoc21main-p374-p (type: Full Paper) doi:10.1145/3406325.3451102

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

Publisher's Version Article: stoc21main-p27-p (type: Full Paper) doi:10.1145/3406325.3451002

Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs
Marco Bressan
(University of Milan, Italy)

Publisher's Version Article: stoc21main-p147-p (type: Full Paper) doi:10.1145/3406325.3451042

Session 6B

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

Publisher's Version Article: stoc21main-p77-p (type: Full Paper) doi:10.1145/3406325.3451020

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

Publisher's Version Article: stoc21main-p80-p (type: Full Paper) doi:10.1145/3406325.3451136

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

Publisher's Version Article: stoc21main-p285-p (type: Full Paper) doi:10.1145/3406325.3451081

Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan
(Reykjavik University, Iceland; University of Freiburg, Germany; Technion, Israel)

Publisher's Version Article: stoc21main-p317-p (type: Full Paper) doi:10.1145/3406325.3451089

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

Publisher's Version Article: stoc21main-p386-p (type: Full Paper) doi:10.1145/3406325.3451106

Session 7B

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

Publisher's Version Article: stoc21main-p344-p (type: Full Paper) doi:10.1145/3406325.3451098

Efficient Randomized DCAS
George Giakkoupis, Mehrdad Jafari Giv, and Philipp Woelfel
(Inria, France; University of Rennes, France; CNRS, France; IRISA, France; University of Calgary, Canada)

Publisher's Version Article: stoc21main-p497-p (type: Full Paper) doi:10.1145/3406325.3451133

Optimal Error Resilience of Adaptive Message Exchange
Klim Efremenko, Gillat Kol, and Raghuvansh R. Saxena
(Ben-Gurion University of the Negev, Israel; Princeton University, USA)

Publisher's Version Article: stoc21main-p273-p (type: Full Paper) doi:10.1145/3406325.3451077

How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games
William Kuszmaul
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p117-p (type: Full Paper) doi:10.1145/3406325.3451033

Load Balancing with Dynamic Set of Balls and Bins
Anders Aamand, Jakob Bæk Tejs Knudsen, and Mikkel Thorup
(University of Copenhagen, Denmark)

Publisher's Version Article: stoc21main-p394-p (type: Full Paper) doi:10.1145/3406325.3451107

Session 6C

Fiber Bundle Codes: Breaking the N^1/2 polylog(N) Barrier for Quantum LDPC Codes
Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell
(Station Q, USA; Microsoft Quantum, USA; Carnegie Mellon University, USA)

Publisher's Version Article: stoc21main-p32-p (type: Full Paper) doi:10.1145/3406325.3451005

An Optimal Separation of Randomized and Quantum Query Complexity
Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu
(University of California at Los Angeles, USA)

Publisher's Version Article: stoc21main-p75-p (type: Full Paper) doi:10.1145/3406325.3451019

k-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal and Makrand Sinha
(CWI, Netherlands; Eindhoven University of Technology, Netherlands)

Publisher's Version Article: stoc21main-p141-p (type: Full Paper) doi:10.1145/3406325.3451040

New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√n log^k n) Distance
Tali Kaufman and Ran J. Tessler
(Bar-Ilan University, Israel; Weizmann Institute of Science, Israel)

Publisher's Version Article: stoc21main-p99-p (type: Full Paper) doi:10.1145/3406325.3451029

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

Publisher's Version Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047

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

Publisher's Version Article: stoc21main-p171-p (type: Full Paper) doi:10.1145/3406325.3451051

Session 7C

(Sub)Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem
András Gilyén, Matthew B. Hastings, and Umesh Vazirani
(California Institute of Technology, USA; Microsoft Quantum, USA; Microsoft Research, USA; University of California at Berkeley, USA)

Publisher's Version Article: stoc21main-p194+p370-p (type: Full Paper) doi:10.1145/3406325.3451060

Succinct Blind Quantum Computation using a Random Oracle
Jiayu Zhang
(Boston University, USA)

Publisher's Version Article: stoc21main-p302-p (type: Full Paper) doi:10.1145/3406325.3451082

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

Publisher's Version Article: stoc21main-p332-p (type: Full Paper) doi:10.1145/3406325.3451094

Improved Quantum Data Analysis
Costin Bădescu and Ryan O'Donnell
(Carnegie Mellon University, USA)

Publisher's Version Article: stoc21main-p404-p (type: Full Paper) doi:10.1145/3406325.3451109

Session 8A

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

Publisher's Version Article: stoc21main-p113-p (type: Full Paper) doi:10.1145/3406325.3451031

Settling the Complexity of Nash Equilibrium in Congestion Games
Yakov Babichenko and Aviad Rubinstein
(Technion, Israel; Stanford University, USA)

Publisher's Version Article: stoc21main-p132-p (type: Full Paper) doi:10.1145/3406325.3451039

Revelation Gap for Pricing from Samples
Yiding Feng, Jason D. Hartline, and Yingkai Li
(Northwestern University, USA)

Publisher's Version Article: stoc21main-p189-p (type: Full Paper) doi:10.1145/3406325.3451057

Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser
(Google Research, Switzerland; Sapienza University of Rome, Italy)

Publisher's Version Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076

The Complexity of Constrained Min-Max Optimization
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis
(Massachusetts Institute of Technology, USA; Singapore University of Technology and Design, Singapore; University of California at Berkeley, USA)

Publisher's Version Article: stoc21main-p470-p (type: Full Paper) doi:10.1145/3406325.3451125

Session 9A

On Codes Decoding a Constant Fraction of Errors on the BSC
Jan Hązła, Alex Samorodnitsky, and Ori Sberlo
(EPFL, Switzerland; Hebrew University of Jerusalem, Israel; Tel Aviv University, Israel)

Publisher's Version Article: stoc21main-p63-p (type: Full Paper) doi:10.1145/3406325.3451015

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

Publisher's Version Article: stoc21main-p97-p (type: Full Paper) doi:10.1145/3406325.3451027

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

Publisher's Version Article: stoc21main-p156-p (type: Full Paper) doi:10.1145/3406325.3451046

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

Publisher's Version Article: stoc21main-p165-p (type: Full Paper) doi:10.1145/3406325.3451048

Near-Linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity
Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani
(University of Chicago, USA; Toyota Technological Institute at Chicago, USA)

Publisher's Version Article: stoc21main-p474-p (type: Full Paper) doi:10.1145/3406325.3451126

Session 8B

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

Publisher's Version Article: stoc21main-p121-p (type: Full Paper) doi:10.1145/3406325.3451035

Entropy Decay in the Swendsen–Wang Dynamics on ℤ^d
Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda
(Pennsylvania State University, USA; Roma Tre University, Italy; University of California at Berkeley, USA; Georgia Institute of Technology, USA)

Publisher's Version Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095

Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, and Yitong Yin
(Nanjing University, China; Institute of Computing Technology at Chinese Academy of Sciences, China; University of Chinese Academy of Sciences, China)

Publisher's Version Article: stoc21main-p369-p (type: Full Paper) doi:10.1145/3406325.3451101

Frozen 1-RSB Structure of the Symmetric Ising Perceptron
Will Perkins and Changji Xu
(University of Illinois at Chicago, USA; Harvard University, USA)

Publisher's Version Article: stoc21main-p444-p (type: Full Paper) doi:10.1145/3406325.3451119

Perfectly Sampling k ≥ (8/3 + o(1))Δ-Colorings in Graphs
Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney
(Simons Institute for the Theory of Computing Berkeley, USA; Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p56-p (type: Full Paper) doi:10.1145/3406325.3451012

Session 9B

The Metric Relaxation for 0-Extension Admits an Ω(log^2/3k) Gap
Roy Schwartz and Nitzan Tur
(Technion, Israel)

Publisher's Version Article: stoc21main-p246-p (type: Full Paper) doi:10.1145/3406325.3451071

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

Publisher's Version Article: stoc21main-p29-p (type: Full Paper) doi:10.1145/3406325.3451003

Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer
(Harvard University, USA; Carnegie Mellon University, USA; Stanford University, USA; ETH Zurich, Switzerland)

Publisher's Version Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099

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

Publisher's Version Article: stoc21main-p168-p (type: Full Paper) doi:10.1145/3406325.3451049

Local Concentration Inequalities and Tomaszewski’s Conjecture
Nathan Keller and Ohad Klein
(Bar-Ilan University, Israel)

Publisher's Version Article: stoc21main-p55-p (type: Full Paper) doi:10.1145/3406325.3451011

Session 8C

Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof and Karol Węgrzycki
(Utrecht University, Netherlands; Saarland University, Germany; MPI-INF, Germany)

Publisher's Version Article: stoc21main-p84-p (type: Full Paper) doi:10.1145/3406325.3451024

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

Publisher's Version Article: stoc21main-p155-p (type: Full Paper) doi:10.1145/3406325.3451045

Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard and Nicole Wein
(Massachusetts Institute of Technology, USA)

Publisher's Version Article: stoc21main-p489-p (type: Full Paper) doi:10.1145/3406325.3451130

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, and Vasileios Nakos
(Saarland University, Germany; MPI-INF, Germany)

Publisher's Version Article: stoc21main-p318-p (type: Full Paper) doi:10.1145/3406325.3451090

Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
(Weizmann Institute of Science, Israel)

Publisher's Version Article: stoc21main-p262-p (type: Full Paper) doi:10.1145/3406325.3451073

Approximate Gomory–Hu Tree Is Faster Than n – 1 Max-Flows
Jason Li and Debmalya Panigrahi
(Carnegie Mellon University, USA; Duke University, USA)

Publisher's Version Article: stoc21main-p417-p (type: Full Paper) doi:10.1145/3406325.3451112

Session 9C

Constant Approximating k-Clique Is W[1]-Hard
Bingkai Lin
(Nanjing University, China)

Publisher's Version Article: stoc21main-p65-p (type: Full Paper) doi:10.1145/3406325.3451016

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

Publisher's Version Article: stoc21main-p239-p (type: Full Paper) doi:10.1145/3406325.3451068

A Full Complexity Dichotomy for Immanant Families
Radu Curticapean
(IT University of Copenhagen, Denmark)

Publisher's Version Article: stoc21main-p467-p (type: Full Paper) doi:10.1145/3406325.3451124

A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, and Guanghao Ye
(University of Washington, USA; Microsoft Research, USA)

Publisher's Version Article: stoc21main-p185-p (type: Full Paper) doi:10.1145/3406325.3451056

proc time: 0.4