STOC 2021 – Proceedings

Frontmatter

Invited Presentations

Keynote

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

@InProceedings{STOC21p1, author = {Alfred V. Aho}, title = {Computational Thinking in Programming Language and Compiler Design (Keynote)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1-0}, doi = {10.1145/3406325.3465350}, year = {2021}, } 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)

@InProceedings{STOC21p5, author = {Leonid A. Levin}, title = {Climbing Algorithms (Invited Talk)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {5-4}, doi = {10.1145/3406325.3457137}, year = {2021}, } 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)

@InProceedings{STOC21p9, author = {Marcelo Arenas and Luis Alberto Croquevielle and Rajesh Jayaram and Cristian Riveros}, title = {A Polynomial-Time Approximation Algorithm for Counting Words Accepted by an NFA (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {9-8}, doi = {10.1145/3406325.3465353}, year = {2021}, } 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)

@InProceedings{STOC21p13, author = {C. J. Argue and Anupam Gupta and Guru Guruganesh and Ziye Tang}, title = {Chasing Convex Bodies with Linear Competitive Ratio (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {13-12}, doi = {10.1145/3406325.3465354}, year = {2021}, } 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)

@InProceedings{STOC21p17, author = {Arthur Jacot and Franck Gabriel and Clément Hongler}, title = {Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {17-16}, doi = {10.1145/3406325.3465355}, year = {2021}, } 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)

@InProceedings{STOC21p21, author = {Jon Kleinberg and Sendhil Mullainathan}, title = {Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {21-20}, doi = {10.1145/3406325.3465356}, year = {2021}, } 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)

@InProceedings{STOC21p25, author = {Isaac H. Kim and Eugene Tang and John Preskill}, title = {The Ghost in the Radiation: Robust Encodings of the Black Hole Interior (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {25-24}, doi = {10.1145/3406325.3465357}, year = {2021}, } 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)

@InProceedings{STOC21p29, author = {Christopher Jung and Katrina Ligett and Seth Neel and Aaron Roth and Saeed Sharifi-Malvajerdi and Moshe Shenfeld}, title = {A New Analysis of Differential Privacy’s Generalization Guarantees (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {29-28}, doi = {10.1145/3406325.3465358}, year = {2021}, } 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)

@InProceedings{STOC21p33, author = {Isaac Grosof and Ziv Scully and Mor Harchol-Balter}, title = {Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {33-32}, doi = {10.1145/3406325.3465359}, year = {2021}, } 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)

@InProceedings{STOC21p37, author = {Shai Ben-David and Pavel Hrubes and Shay Moran and Amir Shpilka and Amir Yehudayoff}, title = {Learnability Can Be Independent of Set Theory (Invited Paper)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {37-36}, doi = {10.1145/3406325.3465360}, year = {2021}, } 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)

@InProceedings{STOC21p41, author = {Nima Anari and Cynthia Vinzant}, title = {Log-Concave Polynomials in Theory and Applications (Tutorial)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {41-40}, doi = {10.1145/3406325.3465351}, year = {2021}, } 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)

@InProceedings{STOC21p45, author = {Nike Sun}, title = {Statistical Physics of Random CSPs (Tutorial)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {45-44}, doi = {10.1145/3406325.3465352}, year = {2021}, } 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)

@InProceedings{STOC21p49, author = {Ryan Alweiss and Yang P. Liu and Mehtaab Sawhney}, title = {Discrepancy Minimization via a Self-Balancing Walk}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {49-48}, doi = {10.1145/3406325.3450994}, year = {2021}, } 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)

@InProceedings{STOC21p63, author = {Zachary Chase}, title = {Separating Words and Trace Reconstruction}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {63-62}, doi = {10.1145/3406325.3451118}, year = {2021}, } 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)

@InProceedings{STOC21p77, author = {Anna R. Karlin and Nathan Klein and Shayan Oveis Gharan}, title = {A (Slightly) Improved Approximation Algorithm for Metric TSP}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {77-76}, doi = {10.1145/3406325.3451009}, year = {2021}, } 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)

@InProceedings{STOC21p91, author = {John Fearnley and Paul W. Goldberg and Alexandros Hollender and Rahul Savani}, title = {The Complexity of Gradient Descent: CLS = PPAD ∩ PLS}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {91-90}, doi = {10.1145/3406325.3451052}, year = {2021}, } 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)

@InProceedings{STOC21p105, author = {Aayush Jain and Huijia Lin and Amit Sahai}, title = {Indistinguishability Obfuscation from Well-Founded Assumptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {105-104}, doi = {10.1145/3406325.3451093}, year = {2021}, } 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)

@InProceedings{STOC21p119, author = {Yufei Ruan and Jiaqi Yang and Yuan Zhou}, title = {Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {119-118}, doi = {10.1145/3406325.3451004}, year = {2021}, } 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)

@InProceedings{STOC21p133, author = {Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis}, title = {Efficiently Learning Halfspaces with Tsybakov Noise}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {133-132}, doi = {10.1145/3406325.3450998}, year = {2021}, } 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)

@InProceedings{STOC21p147, author = {Ainesh Bakshi and Adarsh Prasad}, title = {Robust Linear Regression: Optimal Rates in Polynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {147-146}, doi = {10.1145/3406325.3451001}, year = {2021}, } 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)

@InProceedings{STOC21p161, author = {Eddie Aamari and Alexander Knop}, title = {Statistical Query Complexity of Manifold Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {161-160}, doi = {10.1145/3406325.3451135}, year = {2021}, } 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)

@InProceedings{STOC21p175, author = {Gavin Brown and Mark Bun and Vitaly Feldman and Adam Smith and Kunal Talwar}, title = {When Is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {175-174}, doi = {10.1145/3406325.3451131}, year = {2021}, } 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)

@InProceedings{STOC21p189, author = {Constantinos Daskalakis and Qinxuan Pan}, title = {Sample-Optimal and Efficient Learning of Tree Ising Models}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {189-188}, doi = {10.1145/3406325.3451006}, year = {2021}, } 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)

@InProceedings{STOC21p203, author = {Arnab Bhattacharyya and Sutanu Gayen and Eric Price and N. V. Vinodchandran}, title = {Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {203-202}, doi = {10.1145/3406325.3451066}, year = {2021}, } 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)

@InProceedings{STOC21p217, author = {Yuval Dagan and Constantinos Daskalakis and Nishanth Dikkala and Anthimos Vardis Kandiros}, title = {Learning Ising Models from One or Multiple Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {217-216}, doi = {10.1145/3406325.3451074}, year = {2021}, } 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)

@InProceedings{STOC21p231, author = {Vincent Cohen-Addad and David Saulpic and Chris Schwiegelshohn}, title = {A New Coreset Framework for Clustering}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {231-230}, doi = {10.1145/3406325.3451022}, year = {2021}, } 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)

@InProceedings{STOC21p245, author = {Badih Ghazi and Noah Golowich and Ravi Kumar and Pasin Manurangsi}, title = {Sample-Efficient Proper PAC Learning with Approximate Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {245-244}, doi = {10.1145/3406325.3451028}, year = {2021}, } 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)

@InProceedings{STOC21p259, author = {Alexander Knop and Shachar Lovett and Sam McGuire and Weiqiang Yuan}, title = {Log-Rank and Lifting for AND-Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {259-258}, doi = {10.1145/3406325.3450999}, year = {2021}, } 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)

@InProceedings{STOC21p273, author = {Susanna F. de Rezende and Mika Göös and Jakob Nordström and Toniann Pitassi and Robert Robere and Dmitry Sokolov}, title = {Automating Algebraic Proof Systems Is NP-Hard}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {273-272}, doi = {10.1145/3406325.3451080}, year = {2021}, } 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)

@InProceedings{STOC21p287, author = {Ján Pich and Rahul Santhanam}, title = {Strong Co-nondeterministic Lower Bounds for NP Cannot Be Proved Feasibly}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {287-286}, doi = {10.1145/3406325.3451117}, year = {2021}, } 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)

@InProceedings{STOC21p301, author = {Rahul Santhanam and Iddo Tzameret}, title = {Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {301-300}, doi = {10.1145/3406325.3451010}, year = {2021}, } 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)

@InProceedings{STOC21p315, author = {Mark Braverman and Dor Minzer}, title = {New Separations Results for External Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {315-314}, doi = {10.1145/3406325.3451044}, year = {2021}, } 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)

@InProceedings{STOC21p329, author = {Shir Peleg and Amir Shpilka}, title = {Polynomial Time Deterministic Identity Testing Algorithm for Σ^[3]ΠΣΠ^[2] Circuits via Edelstein–Kelly Type Theorem for Quadratic Polynomials}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {329-328}, doi = {10.1145/3406325.3451013}, year = {2021}, } 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)

@InProceedings{STOC21p343, author = {Zander Kelley}, title = {An Improved Derandomization of the Switching Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {343-342}, doi = {10.1145/3406325.3451054}, year = {2021}, } 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)

@InProceedings{STOC21p357, author = {Lijie Chen and Roei Tell}, title = {Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {357-356}, doi = {10.1145/3406325.3451059}, year = {2021}, } 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)

@InProceedings{STOC21p371, author = {Shuichi Hirahara}, title = {Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {371-370}, doi = {10.1145/3406325.3451065}, year = {2021}, } 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)

@InProceedings{STOC21p385, author = {Zhenjian Lu and Igor C. Oliveira and Rahul Santhanam}, title = {Pseudodeterministic Algorithms and the Structure of Probabilistic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {385-384}, doi = {10.1145/3406325.3451085}, year = {2021}, } 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)

@InProceedings{STOC21p399, author = {Jason Li and Danupon Nanongkai and Debmalya Panigrahi and Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai}, title = {Vertex Connectivity in Poly-logarithmic Max-Flows}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {399-398}, doi = {10.1145/3406325.3451088}, year = {2021}, } 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)

@InProceedings{STOC21p413, author = {Peter Gartland and Daniel Lokshtanov and Marcin Pilipczuk and Michał Pilipczuk and Paweł Rzążewski}, title = {Finding Large Induced Sparse Subgraphs in <i>C_>t</i> -Free Graphs in Quasipolynomial Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {413-412}, doi = {10.1145/3406325.3451034}, year = {2021}, } 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)

@InProceedings{STOC21p427, author = {Arnold Filtser and Hung Le}, title = {Clan Embeddings into Trees, and Low Treewidth Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {427-426}, doi = {10.1145/3406325.3451043}, year = {2021}, } 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)

@InProceedings{STOC21p441, author = {Bernhard Haeupler and D. Ellis Hershkowitz and Goran Zuzic}, title = {Tree Embeddings for Hop-Constrained Network Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {441-440}, doi = {10.1145/3406325.3451053}, year = {2021}, } 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)

@InProceedings{STOC21p455, author = {Federica Cecchetto and Vera Traub and Rico Zenklusen}, title = {Bridging the Gap between Tree and Connectivity Augmentation: Unified and Stronger Approaches}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {455-454}, doi = {10.1145/3406325.3451086}, year = {2021}, } 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)

@InProceedings{STOC21p469, author = {Jason Li}, title = {Deterministic Mincut in Almost-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {469-468}, doi = {10.1145/3406325.3451114}, year = {2021}, } 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)

@InProceedings{STOC21p483, author = {Theo McKenzie and Peter Michael Reichstein Rasmussen and Nikhil Srivastava}, title = {Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {483-482}, doi = {10.1145/3406325.3451129}, year = {2021}, } 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)

@InProceedings{STOC21p497, author = {Nima Anari and Kuikui Liu and Shayan Oveis Gharan and Cynthia Vinzant and Thuy-Duong Vuong}, title = {Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {497-496}, doi = {10.1145/3406325.3451091}, year = {2021}, } 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)

@InProceedings{STOC21p511, author = {Joakim Blikstad and Jan van den Brand and Sagnik Mukhopadhyay and Danupon Nanongkai}, title = {Breaking the Quadratic Barrier for Matroid Intersection}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {511-510}, doi = {10.1145/3406325.3451092}, year = {2021}, } 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)

@InProceedings{STOC21p525, author = {Yeganeh Alimohammadi and Nima Anari and Kirankumar Shiragur and Thuy-Duong Vuong}, title = {Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {525-524}, doi = {10.1145/3406325.3451123}, year = {2021}, } 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)

@InProceedings{STOC21p539, author = {Noga Alon and Omri Ben-Eliezer and Yuval Dagan and Shay Moran and Moni Naor and Eylon Yogev}, title = {Adversarial Laws of Large Numbers and Optimal Regret in Online Classification}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {539-538}, doi = {10.1145/3406325.3451041}, year = {2021}, } 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)

@InProceedings{STOC21p553, author = {Mingda Qiao and Gregory Valiant}, title = {Stronger Calibration Lower Bounds via Sidestepping}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {553-552}, doi = {10.1145/3406325.3451050}, year = {2021}, } 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)

@InProceedings{STOC21p567, author = {Suprovat Ghoshal and Rishi Saket}, title = {Hardness of Learning DNFs using Halfspaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {567-566}, doi = {10.1145/3406325.3451067}, year = {2021}, } 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)

@InProceedings{STOC21p581, author = {Noga Alon and Alon Gonen and Elad Hazan and Shay Moran}, title = {Boosting Simple Learners}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {581-580}, doi = {10.1145/3406325.3451030}, year = {2021}, } 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)

@InProceedings{STOC21p595, author = {Sitan Chen and Ankur Moitra}, title = {Algorithmic Foundations for the Diffraction Limit}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {595-594}, doi = {10.1145/3406325.3451078}, year = {2021}, } 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)

@InProceedings{STOC21p609, author = {Eric Blais and Renato Ferreira Pinto Jr. and Nathaniel Harms}, title = {VC Dimension and Distribution-Free Sample-Based Testing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {609-608}, doi = {10.1145/3406325.3451104}, year = {2021}, } 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)

@InProceedings{STOC21p623, author = {Allen Liu and Ankur Moitra}, title = {Settling the Robust Learnability of Mixtures of Gaussians}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {623-622}, doi = {10.1145/3406325.3451084}, year = {2021}, } 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)

@InProceedings{STOC21p637, author = {Olivier Bousquet and Steve Hanneke and Shay Moran and Ramon van Handel and Amir Yehudayoff}, title = {A Theory of Universal Learning}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {637-636}, doi = {10.1145/3406325.3451087}, year = {2021}, } 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)

@InProceedings{STOC21p651, author = {Ilias Diakonikolas and Themis Gouleakis and Daniel M. Kane and John Peebles and Eric Price}, title = {Optimal Testing of Discrete Distributions with High Probability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {651-650}, doi = {10.1145/3406325.3450997}, year = {2021}, } 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)

@InProceedings{STOC21p665, author = {Seth Pettie and Dingyu Wang}, title = {Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {665-664}, doi = {10.1145/3406325.3451032}, year = {2021}, } 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)

@InProceedings{STOC21p679, author = {Lijie Chen and Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena and Zhao Song and Huacheng Yu}, title = {Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {679-678}, doi = {10.1145/3406325.3451038}, year = {2021}, } 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)

@InProceedings{STOC21p693, author = {Anindya De and Elchanan Mossel and Joe Neeman}, title = {Robust Testing of Low Dimensional Functions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {693-692}, doi = {10.1145/3406325.3451115}, year = {2021}, } 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)

@InProceedings{STOC21p707, author = {Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida}, title = {Towards Tight Bounds for Spectral Sparsification of Hypergraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {707-706}, doi = {10.1145/3406325.3451061}, year = {2021}, } 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)

@InProceedings{STOC21p721, author = {Sepehr Assadi and Vishvajeet N}, title = {Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {721-720}, doi = {10.1145/3406325.3451110}, year = {2021}, } 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)

@InProceedings{STOC21p735, author = {Julia Chuzhoy}, title = {Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {735-734}, doi = {10.1145/3406325.3451025}, year = {2021}, } 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)

@InProceedings{STOC21p749, author = {Tomasz Kociumaka and Saeed Seddighin}, title = {Improved Dynamic Algorithms for Longest Increasing Subsequence}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {749-748}, doi = {10.1145/3406325.3451026}, year = {2021}, } 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)

@InProceedings{STOC21p763, author = {Paweł Gawrychowski and Wojciech Janczewski}, title = {Fully Dynamic Approximation of LIS in Polylogarithmic Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {763-762}, doi = {10.1145/3406325.3451137}, year = {2021}, } 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)

@InProceedings{STOC21p777, author = {Aaron Bernstein and Aditi Dudeja and Zachary Langley}, title = {A Framework for Dynamic Matching in Weighted Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {777-776}, doi = {10.1145/3406325.3451113}, year = {2021}, } 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)

@InProceedings{STOC21p791, author = {Zhiyi Huang and Xinkai Shu}, title = {Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {791-790}, doi = {10.1145/3406325.3451079}, year = {2021}, } 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)

@InProceedings{STOC21p805, author = {Joan Bruna and Oded Regev and Min Jae Song and Yi Tang}, title = {Continuous LWE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {805-804}, doi = {10.1145/3406325.3451000}, year = {2021}, } 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)

@InProceedings{STOC21p819, author = {Ruta Jawale and Yael Tauman Kalai and Dakshita Khurana and Rachel Zhang}, title = {SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {819-818}, doi = {10.1145/3406325.3451055}, year = {2021}, } 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)

@InProceedings{STOC21p833, author = {Yanyi Liu and Rafael Pass}, title = {Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {833-832}, doi = {10.1145/3406325.3451121}, year = {2021}, } 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)

@InProceedings{STOC21p847, author = {Romain Gay and Rafael Pass}, title = {Indistinguishability Obfuscation from Circular Security}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {847-846}, doi = {10.1145/3406325.3451070}, year = {2021}, } 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)

@InProceedings{STOC21p861, author = {Justin Holmgren and Alex Lombardi and Ron D. Rothblum}, title = {Fiat–Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW Is Not Zero-Knowledge)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {861-860}, doi = {10.1145/3406325.3451116}, year = {2021}, } 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)

@InProceedings{STOC21p875, author = {Lijie Chen and Xin Lyu}, title = {Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {875-874}, doi = {10.1145/3406325.3451132}, year = {2021}, } 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)

@InProceedings{STOC21p889, author = {Josh Alman}, title = {Kronecker Products, Low-Depth Circuits, and Matrix Rigidity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {889-888}, doi = {10.1145/3406325.3451008}, year = {2021}, } 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)

@InProceedings{STOC21p903, author = {Arkadev Chattopadhyay and Rajit Datta and Partha Mukhopadhyay}, title = {Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {903-902}, doi = {10.1145/3406325.3451069}, year = {2021}, } 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)

@InProceedings{STOC21p917, author = {Alex Cohen and Guy Moshkovitz}, title = {Structure vs. Randomness for Bilinear Maps}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {917-916}, doi = {10.1145/3406325.3451007}, year = {2021}, } 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)

@InProceedings{STOC21p931, author = {Vishwas Bhargava and Shubhangi Saraf and Ilya Volkovich}, title = {Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {931-930}, doi = {10.1145/3406325.3451096}, year = {2021}, } 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)

@InProceedings{STOC21p945, author = {Shunhua Jiang and Zhao Song and Omri Weinstein and Hengjie Zhang}, title = {A Faster Algorithm for Solving General LPs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {945-944}, doi = {10.1145/3406325.3451058}, year = {2021}, } 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)

@InProceedings{STOC21p959, author = {Rad Niazadeh and Renato Paes Leme and Jon Schneider}, title = {Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {959-958}, doi = {10.1145/3406325.3451072}, year = {2021}, } 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)

@InProceedings{STOC21p973, author = {Leonid Gurvits and Jonathan Leake}, title = {Capacity Lower Bounds via Productization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {973-972}, doi = {10.1145/3406325.3451105}, year = {2021}, } 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)

@InProceedings{STOC21p987, author = {Jan van den Brand and Yin Tat Lee and Yang P. Liu and Thatchaphol Saranurak and Aaron Sidford and Zhao Song and Di Wang}, title = {Minimum Cost Flows, MDPs, and ℓ₁-Regression in Nearly Linear Time for Dense Instances}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {987-986}, doi = {10.1145/3406325.3451108}, year = {2021}, } 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)

@InProceedings{STOC21p1001, author = {Vijay Bhattiprolu and Euiwoong Lee and Assaf Naor}, title = {A Framework for Quadratic Form Maximization over Convex Sets through Nonconvex Relaxations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1001-1000}, doi = {10.1145/3406325.3451128}, year = {2021}, } 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)

@InProceedings{STOC21p1015, author = {Aviad Rubinstein and Junyao Zhao}, title = {The Randomized Communication Complexity of Randomized Auctions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1015-1014}, doi = {10.1145/3406325.3451111}, year = {2021}, } 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)

@InProceedings{STOC21p1029, author = {Oren Mangoubi and Nisheeth K. Vishnoi}, title = {Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1029-1028}, doi = {10.1145/3406325.3451097}, year = {2021}, } 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)

@InProceedings{STOC21p1043, author = {Akshay Krishnamurthy and Thodoris Lykouris and Chara Podimata and Robert Schapire}, title = {Contextual Search in the Presence of Irrational Agents}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1043-1042}, doi = {10.1145/3406325.3451120}, year = {2021}, } 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)

@InProceedings{STOC21p1057, author = {Maria-Florina Balcan and Dan DeBlasio and Travis Dick and Carl Kingsford and Tuomas Sandholm and Ellen Vitercik}, title = {How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1057-1056}, doi = {10.1145/3406325.3451036}, year = {2021}, } 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)

@InProceedings{STOC21p1071, author = {Shahar Dobzinski and Shiri Ron}, title = {The Communication Complexity of Payment Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1071-1070}, doi = {10.1145/3406325.3451083}, year = {2021}, } 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)

@InProceedings{STOC21p1085, author = {Aviad Rubinstein and Raghuvansh R. Saxena and Clayton Thomas and S. Matthew Weinberg and Junyao Zhao}, title = {Exponential Communication Separations between Notions of Selfishness}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1085-1084}, doi = {10.1145/3406325.3451127}, year = {2021}, } 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)

@InProceedings{STOC21p1099, author = {He Jia and Aditi Laddha and Yin Tat Lee and Santosh Vempala}, title = {Reducing Isotropy and Volume to KLS: An <i>O</i>*(<i>n</i>³<i>ψ</i>²) Volume Algorithm}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1099-1098}, doi = {10.1145/3406325.3451018}, year = {2021}, } 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)

@InProceedings{STOC21p1113, author = {Haitao Wang}, title = {A New Algorithm for Euclidean Shortest Paths in the Plane}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1113-1112}, doi = {10.1145/3406325.3451037}, year = {2021}, } 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)

@InProceedings{STOC21p1127, author = {Natan Rubin}, title = {Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1127-1126}, doi = {10.1145/3406325.3451062}, year = {2021}, } 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)

@InProceedings{STOC21p1141, author = {Yakov Nekrich}, title = {Dynamic Planar Point Location in Optimal Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1141-1140}, doi = {10.1145/3406325.3451100}, year = {2021}, } 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)

@InProceedings{STOC21p1155, author = {Marcelo Arenas and Luis Alberto Croquevielle and Rajesh Jayaram and Cristian Riveros}, title = {When Is Approximate Counting for Conjunctive Queries Tractable?}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1155-1154}, doi = {10.1145/3406325.3451014}, year = {2021}, } 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)

@InProceedings{STOC21p1169, author = {Yair Bartal and Lee-Ad Gottlieb}, title = {Near-Linear Time Approximation Schemes for Steiner Tree and Forest in Low-Dimensional Spaces}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1169-1168}, doi = {10.1145/3406325.3451063}, year = {2021}, } 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)

@InProceedings{STOC21p1183, author = {Lars Rohwedder and Andreas Wiese}, title = {A (2 + <i>ε</i>)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1183-1182}, doi = {10.1145/3406325.3451075}, year = {2021}, } 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)

@InProceedings{STOC21p1197, author = {Vincent Cohen-Addad and Anupam Gupta and Philip N. Klein and Jason Li}, title = {A Quasipolynomial (2 + <i>ε</i>)-Approximation for Planar Sparsest Cut}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1197-1196}, doi = {10.1145/3406325.3451103}, year = {2021}, } 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)

@InProceedings{STOC21p1211, author = {Yossi Azar and Stefano Leonardi and Noam Touitou}, title = {Flow Time Scheduling with Uncertain Processing Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1211-1210}, doi = {10.1145/3406325.3451023}, year = {2021}, } 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)

@InProceedings{STOC21p1225, author = {Albert Cheu and Jonathan Ullman}, title = {The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1225-1224}, doi = {10.1145/3406325.3450995}, year = {2021}, } 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)

@InProceedings{STOC21p1239, author = {Cynthia Dwork and Michael P. Kim and Omer Reingold and Guy N. Rothblum and Gal Yona}, title = {Outcome Indistinguishability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1239-1238}, doi = {10.1145/3406325.3451064}, year = {2021}, } 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)

@InProceedings{STOC21p1253, author = {Marthe Bonamy and Louis Esperet and Carla Groenland and Alex Scott}, title = {Optimal Labelling Schemes for Adjacency, Comparability, and Reachability}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1253-1252}, doi = {10.1145/3406325.3451102}, year = {2021}, } 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)

@InProceedings{STOC21p1267, author = {Gal Beniamini and Noam Nisan}, title = {Bipartite Perfect Matching as a Real Polynomial}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1267-1266}, doi = {10.1145/3406325.3451002}, year = {2021}, } 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)

@InProceedings{STOC21p1281, author = {Marco Bressan}, title = {Efficient and Near-Optimal Algorithms for Sampling Connected Subgraphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1281-1280}, doi = {10.1145/3406325.3451042}, year = {2021}, } 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)

@InProceedings{STOC21p1295, author = {Michal Dory and Yuval Efron and Sagnik Mukhopadhyay and Danupon Nanongkai}, title = {Distributed Weighted Min-Cut in Nearly-Optimal Time}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1295-1294}, doi = {10.1145/3406325.3451020}, year = {2021}, } 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)

@InProceedings{STOC21p1309, author = {Krzysztof Nowicki}, title = {A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1309-1308}, doi = {10.1145/3406325.3451136}, year = {2021}, } 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)

@InProceedings{STOC21p1323, author = {Bernhard Haeupler and David Wajc and Goran Zuzic}, title = {Universally-Optimal Distributed Algorithms for Known Topologies}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1323-1322}, doi = {10.1145/3406325.3451081}, year = {2021}, } 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)

@InProceedings{STOC21p1337, author = {Magnús M. Halldórsson and Fabian Kuhn and Yannic Maus and Tigran Tonoyan}, title = {Efficient Randomized Distributed Coloring in CONGEST}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1337-1336}, doi = {10.1145/3406325.3451089}, year = {2021}, } 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)

@InProceedings{STOC21p1351, author = {Nachum Dershowitz and Rotem Oshman and Tal Roth}, title = {The Communication Complexity of Multiparty Set Disjointness under Product Distributions}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1351-1350}, doi = {10.1145/3406325.3451106}, year = {2021}, } 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)

@InProceedings{STOC21p1365, author = {Mohsen Ghaffari and Bernhard Haeupler and Goran Zuzic}, title = {Hop-Constrained Oblivious Routing}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1365-1364}, doi = {10.1145/3406325.3451098}, year = {2021}, } 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)

@InProceedings{STOC21p1379, author = {George Giakkoupis and Mehrdad Jafari Giv and Philipp Woelfel}, title = {Efficient Randomized DCAS}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1379-1378}, doi = {10.1145/3406325.3451133}, year = {2021}, } 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)

@InProceedings{STOC21p1393, author = {Klim Efremenko and Gillat Kol and Raghuvansh R. Saxena}, title = {Optimal Error Resilience of Adaptive Message Exchange}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1393-1392}, doi = {10.1145/3406325.3451077}, year = {2021}, } 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)

@InProceedings{STOC21p1407, author = {William Kuszmaul}, title = {How Asymmetry Helps Buffer Management: Achieving Optimal Tail Size in Cup Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1407-1406}, doi = {10.1145/3406325.3451033}, year = {2021}, } 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)

@InProceedings{STOC21p1421, author = {Anders Aamand and Jakob Bæk Tejs Knudsen and Mikkel Thorup}, title = {Load Balancing with Dynamic Set of Balls and Bins}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1421-1420}, doi = {10.1145/3406325.3451107}, year = {2021}, } 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)

@InProceedings{STOC21p1435, author = {Matthew B. Hastings and Jeongwan Haah and Ryan O'Donnell}, title = {Fiber Bundle Codes: Breaking the <i>N</i>^1/2 polylog(<i>N</i>) Barrier for Quantum LDPC Codes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1435-1434}, doi = {10.1145/3406325.3451005}, year = {2021}, } 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)

@InProceedings{STOC21p1449, author = {Alexander A. Sherstov and Andrey A. Storozhenko and Pei Wu}, title = {An Optimal Separation of Randomized and Quantum Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1449-1448}, doi = {10.1145/3406325.3451019}, year = {2021}, } 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)

@InProceedings{STOC21p1463, author = {Nikhil Bansal and Makrand Sinha}, title = {k-Forrelation Optimally Separates Quantum and Classical Query Complexity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1463-1462}, doi = {10.1145/3406325.3451040}, year = {2021}, } 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)

@InProceedings{STOC21p1477, author = {Tali Kaufman and Ran J. Tessler}, title = {New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√<i>n</i> log^<i>k</i> <i>n</i>) Distance}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1477-1476}, doi = {10.1145/3406325.3451029}, year = {2021}, } 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)

@InProceedings{STOC21p1491, author = {Scott Aaronson and Shalev Ben-David and Robin Kothari and Shravas Rao and Avishay Tal}, title = {Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1491-1490}, doi = {10.1145/3406325.3451047}, year = {2021}, } 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)

@InProceedings{STOC21p1505, author = {Bill Fefferman and Zachary Remscrim}, title = {Eliminating Intermediate Measurements in Space-Bounded Quantum Computation}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1505-1504}, doi = {10.1145/3406325.3451051}, year = {2021}, } 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)

@InProceedings{STOC21p1519, author = {András Gilyén and Matthew B. Hastings and Umesh Vazirani}, title = {(Sub)Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1519-1518}, doi = {10.1145/3406325.3451060}, year = {2021}, } 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)

@InProceedings{STOC21p1533, author = {Jiayu Zhang}, title = {Succinct Blind Quantum Computation using a Random Oracle}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1533-1532}, doi = {10.1145/3406325.3451082}, year = {2021}, } 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)

@InProceedings{STOC21p1547, author = {Jonathan Leake and Colin McSwiggen and Nisheeth K. Vishnoi}, title = {Sampling Matrices from Harish-Chandra–Itzykson–Zuber Densities with Applications to Quantum Inference and Differential Privacy}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1547-1546}, doi = {10.1145/3406325.3451094}, year = {2021}, } 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)

@InProceedings{STOC21p1561, author = {Costin Bădescu and Ryan O'Donnell}, title = {Improved Quantum Data Analysis}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1561-1560}, doi = {10.1145/3406325.3451109}, year = {2021}, } 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)

@InProceedings{STOC21p1575, author = {Jugal Garg and Edin Husić and László A. Végh}, title = {Approximating Nash Social Welfare under Rado Valuations}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1575-1574}, doi = {10.1145/3406325.3451031}, year = {2021}, } 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)

@InProceedings{STOC21p1589, author = {Yakov Babichenko and Aviad Rubinstein}, title = {Settling the Complexity of Nash Equilibrium in Congestion Games}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1589-1588}, doi = {10.1145/3406325.3451039}, year = {2021}, } 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)

@InProceedings{STOC21p1603, author = {Yiding Feng and Jason D. Hartline and Yingkai Li}, title = {Revelation Gap for Pricing from Samples}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1603-1602}, doi = {10.1145/3406325.3451057}, year = {2021}, } 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)

@InProceedings{STOC21p1617, author = {Paul Dütting and Federico Fusco and Philip Lazos and Stefano Leonardi and Rebecca Reiffenhäuser}, title = {Efficient Two-Sided Markets with Limited Information}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1617-1616}, doi = {10.1145/3406325.3451076}, year = {2021}, } 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)

@InProceedings{STOC21p1631, author = {Constantinos Daskalakis and Stratis Skoulakis and Manolis Zampetakis}, title = {The Complexity of Constrained Min-Max Optimization}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1631-1630}, doi = {10.1145/3406325.3451125}, year = {2021}, } 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)

@InProceedings{STOC21p1645, author = {Jan Hązła and Alex Samorodnitsky and Ori Sberlo}, title = {On Codes Decoding a Constant Fraction of Errors on the BSC}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1645-1644}, doi = {10.1145/3406325.3451015}, year = {2021}, } 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)

@InProceedings{STOC21p1659, author = {Siddharth Bhandari and Prahladh Harsha and Mrinal Kumar and Madhu Sudan}, title = {Decoding Multivariate Multiplicity Codes on Product Sets}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1659-1658}, doi = {10.1145/3406325.3451027}, year = {2021}, } 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)

@InProceedings{STOC21p1673, author = {Zeyu Guo and Noga Ron-Zewi}, title = {Efficient List-Decoding with Constant Alphabet and List Sizes}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1673-1672}, doi = {10.1145/3406325.3451046}, year = {2021}, } 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)

@InProceedings{STOC21p1687, author = {Ronen Shaltiel and Jad Silbak}, title = {Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1687-1686}, doi = {10.1145/3406325.3451048}, year = {2021}, } 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)

@InProceedings{STOC21p1701, author = {Fernando Granha Jeronimo and Shashank Srivastava and Madhur Tulsiani}, title = {Near-Linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1701-1700}, doi = {10.1145/3406325.3451126}, year = {2021}, } 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)

@InProceedings{STOC21p1715, author = {Zongchen Chen and Kuikui Liu and Eric Vigoda}, title = {Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1715-1714}, doi = {10.1145/3406325.3451035}, year = {2021}, } 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)

@InProceedings{STOC21p1729, author = {Antonio Blanca and Pietro Caputo and Daniel Parisi and Alistair Sinclair and Eric Vigoda}, title = {Entropy Decay in the Swendsen–Wang Dynamics on ℤ^<i>d</i>}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1729-1728}, doi = {10.1145/3406325.3451095}, year = {2021}, } 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)

@InProceedings{STOC21p1743, author = {Weiming Feng and Kun He and Yitong Yin}, title = {Sampling Constraint Satisfaction Solutions in the Local Lemma Regime}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1743-1742}, doi = {10.1145/3406325.3451101}, year = {2021}, } 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)

@InProceedings{STOC21p1757, author = {Will Perkins and Changji Xu}, title = {Frozen 1-RSB Structure of the Symmetric Ising Perceptron}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1757-1756}, doi = {10.1145/3406325.3451119}, year = {2021}, } 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)

@InProceedings{STOC21p1771, author = {Vishesh Jain and Ashwin Sah and Mehtaab Sawhney}, title = {Perfectly Sampling <i>k</i> ≥ (8/3 + <i>o</i>(1))Δ-Colorings in Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1771-1770}, doi = {10.1145/3406325.3451012}, year = {2021}, } 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)

@InProceedings{STOC21p1785, author = {Roy Schwartz and Nitzan Tur}, title = {The Metric Relaxation for <i>0</i>-Extension Admits an <i>Ω(log^2/3k)</i> Gap}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1785-1784}, doi = {10.1145/3406325.3451071}, year = {2021}, } 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)

@InProceedings{STOC21p1799, author = {Amey Bhangale and Subhash Khot}, title = {Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1799-1798}, doi = {10.1145/3406325.3451003}, year = {2021}, } 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)

@InProceedings{STOC21p1813, author = {Mitali Bafna and Boaz Barak and Pravesh K. Kothari and Tselil Schramm and David Steurer}, title = {Playing Unique Games on Certified Small-Set Expanders}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1813-1812}, doi = {10.1145/3406325.3451099}, year = {2021}, } 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)

@InProceedings{STOC21p1827, author = {Gil Cohen and Noam Peri and Amnon Ta-Shma}, title = {Expander Random Walks: A Fourier-Analytic Approach}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1827-1826}, doi = {10.1145/3406325.3451049}, year = {2021}, } 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)

@InProceedings{STOC21p1841, author = {Nathan Keller and Ohad Klein}, title = {Local Concentration Inequalities and Tomaszewski’s Conjecture}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1841-1840}, doi = {10.1145/3406325.3451011}, year = {2021}, } 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)

@InProceedings{STOC21p1855, author = {Jesper Nederlof and Karol Węgrzycki}, title = {Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1855-1854}, doi = {10.1145/3406325.3451024}, year = {2021}, } 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)

@InProceedings{STOC21p1869, author = {Ray Li}, title = {Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1869-1868}, doi = {10.1145/3406325.3451045}, year = {2021}, } 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)

@InProceedings{STOC21p1883, author = {Mina Dalirrooyfard and Nicole Wein}, title = {Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1883-1882}, doi = {10.1145/3406325.3451130}, year = {2021}, } 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)

@InProceedings{STOC21p1897, author = {Karl Bringmann and Nick Fischer and Vasileios Nakos}, title = {Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1897-1896}, doi = {10.1145/3406325.3451090}, year = {2021}, } 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)

@InProceedings{STOC21p1911, author = {Amir Abboud and Robert Krauthgamer and Ohad Trabelsi}, title = {Subcubic Algorithms for Gomory–Hu Tree in Unweighted Graphs}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1911-1910}, doi = {10.1145/3406325.3451073}, year = {2021}, } 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)

@InProceedings{STOC21p1925, author = {Jason Li and Debmalya Panigrahi}, title = {Approximate Gomory–Hu Tree Is Faster Than <i>n</i> – 1 Max-Flows}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1925-1924}, doi = {10.1145/3406325.3451112}, year = {2021}, } 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)

@InProceedings{STOC21p1939, author = {Bingkai Lin}, title = {Constant Approximating k-Clique Is W[1]-Hard}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1939-1938}, doi = {10.1145/3406325.3451016}, year = {2021}, } 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)

@InProceedings{STOC21p1953, author = {Bart M. P. Jansen and Jari J. H. de Kroon and Michał Włodarczyk}, title = {Vertex Deletion Parameterized by Elimination Distance and Even Less}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1953-1952}, doi = {10.1145/3406325.3451068}, year = {2021}, } 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)

@InProceedings{STOC21p1967, author = {Radu Curticapean}, title = {A Full Complexity Dichotomy for Immanant Families}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1967-1966}, doi = {10.1145/3406325.3451124}, year = {2021}, } 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)

@InProceedings{STOC21p1981, author = {Sally Dong and Yin Tat Lee and Guanghao Ye}, title = {A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path}, booktitle = {Proc.\ STOC}, publisher = {ACM}, pages = {1981-1980}, doi = {10.1145/3406325.3451056}, year = {2021}, } Publisher's Version Article: stoc21main-p185-p (type: Full Paper) doi:10.1145/3406325.3451056

proc time: 0.42