STOC '21: "Load Balancing with Dynamic ..."
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
STOC '21: "Statistical Query Complexity ..."
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
STOC '21: "Degree vs. Approximate Degree ..."
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
STOC '21: "Subcubic Algorithms for Gomory–Hu ..."
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
STOC '21: "Computational Thinking in ..."
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
STOC '21: "Fractionally Log-Concave and ..."
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
STOC '21: "Kronecker Products, Low-Depth ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Boosting Simple Learners ..."
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
STOC '21: "Discrepancy Minimization via ..."
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
STOC '21: "Log-Concave Polynomials in ..."
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
STOC '21: "Log-Concave Polynomials IV: ..."
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
STOC '21: "Fractionally Log-Concave and ..."
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
STOC '21: "A Polynomial-Time Approximation ..."
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
STOC '21: "When Is Approximate Counting ..."
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
STOC '21: "Chasing Convex Bodies with ..."
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
STOC '21: "Graph Streaming Lower Bounds ..."
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
STOC '21: "Flow Time Scheduling with ..."
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
STOC '21: "Settling the Complexity of ..."
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
STOC '21: "Improved Quantum Data Analysis ..."
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
STOC '21: "Playing Unique Games on Certified ..."
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
STOC '21: "Robust Linear Regression: ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "k-Forrelation Optimally Separates ..."
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
STOC '21: "Playing Unique Games on Certified ..."
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
STOC '21: "Near-Linear Time Approximation ..."
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
STOC '21: "Learnability Can Be Independent ..."
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
STOC '21: "Degree vs. Approximate Degree ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Bipartite Perfect Matching ..."
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
STOC '21: "A Framework for Dynamic Matching ..."
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
STOC '21: "Decoding Multivariate Multiplicity ..."
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
STOC '21: "Optimal Inapproximability ..."
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
STOC '21: "Reconstruction Algorithms ..."
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
STOC '21: "Near-Optimal Learning of Tree-Structured ..."
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
STOC '21: "A Framework for Quadratic ..."
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
STOC '21: "VC Dimension and Distribution-Free ..."
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
STOC '21: "Entropy Decay in the Swendsen–Wang ..."
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 ℤ<sup><i>d</i></sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1729-1728},
doi = {10.1145/3406325.3451095},
year = {2021},
}
Publisher's Version
STOC '21: "Breaking the Quadratic Barrier ..."
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
STOC '21: "Optimal Labelling Schemes ..."
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
STOC '21: "A Theory of Universal Learning ..."
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
STOC '21: "New Separations Results for ..."
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
STOC '21: "Efficient and Near-Optimal ..."
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
STOC '21: "Sparse Nonnegative Convolution ..."
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
STOC '21: "When Is Memorization of Irrelevant ..."
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
STOC '21: "Continuous LWE ..."
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
STOC '21: "When Is Memorization of Irrelevant ..."
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
STOC '21: "Entropy Decay in the Swendsen–Wang ..."
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 ℤ<sup><i>d</i></sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1729-1728},
doi = {10.1145/3406325.3451095},
year = {2021},
}
Publisher's Version
STOC '21: "Bridging the Gap between Tree ..."
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
STOC '21: "Separating Words and Trace ..."
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
STOC '21: "Lower Bounds for Monotone ..."
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
STOC '21: "Simple and Fast Derandomization ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "Inverse-Exponential Correlation ..."
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
STOC '21: "Algorithmic Foundations for ..."
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
STOC '21: "Optimal Mixing of Glauber ..."
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
STOC '21: "The Limits of Pan Privacy ..."
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
STOC '21: "Decremental All-Pairs Shortest ..."
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
STOC '21: "Structure vs. Randomness for ..."
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
STOC '21: "Expander Random Walks: A Fourier-Analytic ..."
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
STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
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
STOC '21: "A New Coreset Framework for ..."
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
STOC '21: "A Polynomial-Time Approximation ..."
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
STOC '21: "When Is Approximate Counting ..."
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
STOC '21: "A Full Complexity Dichotomy ..."
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
STOC '21: "Learning Ising Models from ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Tight Conditional Lower Bounds ..."
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
STOC '21: "The Complexity of Constrained ..."
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
STOC '21: "Sample-Optimal and Efficient ..."
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
STOC '21: "Learning Ising Models from ..."
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
STOC '21: "Lower Bounds for Monotone ..."
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
STOC '21: "Robust Testing of Low Dimensional ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "Vertex Deletion Parameterized ..."
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
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "The Communication Complexity ..."
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
STOC '21: "Efficiently Learning Halfspaces ..."
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
STOC '21: "Optimal Testing of Discrete ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "Learning Ising Models from ..."
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
STOC '21: "The Communication Complexity ..."
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
STOC '21: "A Nearly-Linear Time Algorithm ..."
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
STOC '21: "Distributed Weighted Min-Cut ..."
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
STOC '21: "A Framework for Dynamic Matching ..."
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
STOC '21: "Efficient Two-Sided Markets ..."
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
STOC '21: "Outcome Indistinguishability ..."
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
STOC '21: "Optimal Error Resilience of ..."
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
STOC '21: "Distributed Weighted Min-Cut ..."
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
STOC '21: "Optimal Labelling Schemes ..."
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
STOC '21: "The Complexity of Gradient ..."
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
STOC '21: "Eliminating Intermediate Measurements ..."
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
STOC '21: "When Is Memorization of Irrelevant ..."
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
STOC '21: "Sampling Constraint Satisfaction ..."
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
STOC '21: "Revelation Gap for Pricing ..."
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
STOC '21: "VC Dimension and Distribution-Free ..."
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
STOC '21: "Clan Embeddings into Trees, ..."
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
STOC '21: "Sparse Nonnegative Convolution ..."
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
STOC '21: "Efficient Two-Sided Markets ..."
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
STOC '21: "Neural Tangent Kernel: Convergence ..."
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
STOC '21: "Approximating Nash Social ..."
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
STOC '21: "Finding Large Induced Sparse ..."
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<sub>>t</sub></i> -Free Graphs in Quasipolynomial Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {413-412},
doi = {10.1145/3406325.3451034},
year = {2021},
}
Publisher's Version
STOC '21: "Fully Dynamic Approximation ..."
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
STOC '21: "Indistinguishability Obfuscation ..."
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
STOC '21: "Near-Optimal Learning of Tree-Structured ..."
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
STOC '21: "Hop-Constrained Oblivious ..."
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
STOC '21: "Log-Concave Polynomials IV: ..."
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
STOC '21: "A (Slightly) Improved Approximation ..."
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
STOC '21: "Sample-Efficient Proper PAC ..."
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
STOC '21: "Hardness of Learning DNFs ..."
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
STOC '21: "Efficient Randomized DCAS ..."
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
STOC '21: "(Sub)Exponential Advantage ..."
(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
STOC '21: "Efficient Randomized DCAS ..."
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
STOC '21: "The Complexity of Gradient ..."
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
STOC '21: "Sample-Efficient Proper PAC ..."
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
STOC '21: "Boosting Simple Learners ..."
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
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "Near-Linear Time Approximation ..."
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
STOC '21: "Optimal Testing of Discrete ..."
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
STOC '21: "Optimal Labelling Schemes ..."
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
STOC '21: "Load Balancing Guardrails: ..."
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
STOC '21: "Efficient List-Decoding with ..."
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
STOC '21: "Chasing Convex Bodies with ..."
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
STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
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
STOC '21: "Chasing Convex Bodies with ..."
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
STOC '21: "Capacity Lower Bounds via ..."
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
STOC '21: "Fiber Bundle Codes: Breaking ..."
Fiber Bundle Codes: Breaking the N1/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><sup>1/2</sup> 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
STOC '21: "Universally-Optimal Distributed ..."
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
STOC '21: "Hop-Constrained Oblivious ..."
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
STOC '21: "Tree Embeddings for Hop-Constrained ..."
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
STOC '21: "Efficient Randomized Distributed ..."
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
STOC '21: "A Theory of Universal Learning ..."
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
STOC '21: "Load Balancing Guardrails: ..."
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
STOC '21: "VC Dimension and Distribution-Free ..."
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
STOC '21: "Decoding Multivariate Multiplicity ..."
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
STOC '21: "Revelation Gap for Pricing ..."
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
STOC '21: "Fiber Bundle Codes: Breaking ..."
Fiber Bundle Codes: Breaking the N1/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><sup>1/2</sup> 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
STOC '21: "(Sub)Exponential Advantage ..."
(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
STOC '21: "Boosting Simple Learners ..."
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
STOC '21: "On Codes Decoding a Constant ..."
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
STOC '21: "Sampling Constraint Satisfaction ..."
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
STOC '21: "Tree Embeddings for Hop-Constrained ..."
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
STOC '21: "Average-Case Hardness of NP ..."
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
STOC '21: "The Complexity of Gradient ..."
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
STOC '21: "Fiat–Shamir via List-Recoverable ..."
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
STOC '21: "Neural Tangent Kernel: Convergence ..."
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
STOC '21: "Learnability Can Be Independent ..."
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
STOC '21: "Online Stochastic Matching, ..."
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
STOC '21: "Approximating Nash Social ..."
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
STOC '21: "Neural Tangent Kernel: Convergence ..."
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
STOC '21: "Indistinguishability Obfuscation ..."
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
STOC '21: "Perfectly Sampling k ..."
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
STOC '21: "Fully Dynamic Approximation ..."
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
STOC '21: "Vertex Deletion Parameterized ..."
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
STOC '21: "SNARGs for Bounded Depth Computations ..."
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
STOC '21: "A Polynomial-Time Approximation ..."
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
STOC '21: "When Is Approximate Counting ..."
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
STOC '21: "Near-Linear Time Decoding ..."
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
STOC '21: "Reducing Isotropy and Volume ..."
Reducing Isotropy and Volume to KLS: An O*(n3ψ2) 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><sup>3</sup><i>ψ</i><sup>2</sup>) Volume Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1099-1098},
doi = {10.1145/3406325.3451018},
year = {2021},
}
Publisher's Version
STOC '21: "A Faster Algorithm for Solving ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "SNARGs for Bounded Depth Computations ..."
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
STOC '21: "Learning Ising Models from ..."
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
STOC '21: "Efficiently Learning Halfspaces ..."
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
STOC '21: "Optimal Testing of Discrete ..."
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
STOC '21: "Towards Tight Bounds for Spectral ..."
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
STOC '21: "A (Slightly) Improved Approximation ..."
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
STOC '21: "New Cosystolic Expanders from ..."
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√n logk 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<sup><i>k</i></sup> <i>n</i>) Distance},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1477-1476},
doi = {10.1145/3406325.3451029},
year = {2021},
}
Publisher's Version
STOC '21: "Local Concentration Inequalities ..."
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
STOC '21: "An Improved Derandomization ..."
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
STOC '21: "Optimal Inapproximability ..."
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
STOC '21: "SNARGs for Bounded Depth Computations ..."
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
STOC '21: "The Ghost in the Radiation: ..."
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
STOC '21: "Outcome Indistinguishability ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "A (Slightly) Improved Approximation ..."
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
STOC '21: "Local Concentration Inequalities ..."
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
STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
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
STOC '21: "Simplicity Creates Inequity: ..."
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
STOC '21: "Statistical Query Complexity ..."
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
STOC '21: "Log-Rank and Lifting for AND-Functions ..."
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
STOC '21: "Load Balancing with Dynamic ..."
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
STOC '21: "Improved Dynamic Algorithms ..."
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
STOC '21: "Optimal Error Resilience of ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "Efficiently Learning Halfspaces ..."
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
STOC '21: "Playing Unique Games on Certified ..."
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
STOC '21: "Degree vs. Approximate Degree ..."
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
STOC '21: "Subcubic Algorithms for Gomory–Hu ..."
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
STOC '21: "Towards Tight Bounds for Spectral ..."
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
STOC '21: "Contextual Search in the Presence ..."
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
STOC '21: "Efficient Randomized Distributed ..."
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
STOC '21: "Decoding Multivariate Multiplicity ..."
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
STOC '21: "Sample-Efficient Proper PAC ..."
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
STOC '21: "How Asymmetry Helps Buffer ..."
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
STOC '21: "Reducing Isotropy and Volume ..."
Reducing Isotropy and Volume to KLS: An O*(n3ψ2) 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><sup>3</sup><i>ψ</i><sup>2</sup>) Volume Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1099-1098},
doi = {10.1145/3406325.3451018},
year = {2021},
}
Publisher's Version
STOC '21: "A Framework for Dynamic Matching ..."
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
STOC '21: "Efficient Two-Sided Markets ..."
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
STOC '21: "Clan Embeddings into Trees, ..."
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
STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..."
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
STOC '21: "Capacity Lower Bounds via ..."
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
STOC '21: "A Framework for Quadratic ..."
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
STOC '21: "Reducing Isotropy and Volume ..."
Reducing Isotropy and Volume to KLS: An O*(n3ψ2) 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><sup>3</sup><i>ψ</i><sup>2</sup>) Volume Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1099-1098},
doi = {10.1145/3406325.3451018},
year = {2021},
}
Publisher's Version
STOC '21: "A Nearly-Linear Time Algorithm ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "Combinatorial Bernoulli Factories: ..."
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
STOC '21: "Flow Time Scheduling with ..."
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
STOC '21: "Efficient Two-Sided Markets ..."
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
STOC '21: "Climbing Algorithms (Invited ..."
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
STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
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
STOC '21: "Approximate Gomory–Hu Tree ..."
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
STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
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
STOC '21: "Deterministic Mincut in Almost-Linear ..."
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
STOC '21: "Settling SETH vs. Approximate ..."
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
STOC '21: "Revelation Gap for Pricing ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "Constant Approximating k-Clique ..."
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
STOC '21: "Indistinguishability Obfuscation ..."
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
STOC '21: "Settling the Robust Learnability ..."
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
STOC '21: "Optimal Mixing of Glauber ..."
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
STOC '21: "Log-Concave Polynomials IV: ..."
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
STOC '21: "Discrepancy Minimization via ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "Cryptography from Sublinear-Time ..."
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
STOC '21: "Finding Large Induced Sparse ..."
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<sub>>t</sub></i> -Free Graphs in Quasipolynomial Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {413-412},
doi = {10.1145/3406325.3451034},
year = {2021},
}
Publisher's Version
STOC '21: "Fiat–Shamir via List-Recoverable ..."
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
STOC '21: "Log-Rank and Lifting for AND-Functions ..."
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
STOC '21: "Pseudodeterministic Algorithms ..."
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
STOC '21: "Contextual Search in the Presence ..."
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
STOC '21: "Inverse-Exponential Correlation ..."
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
STOC '21: "Greedy Adversarial Equilibrium: ..."
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
STOC '21: "Sample-Efficient Proper PAC ..."
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
STOC '21: "Efficient Randomized Distributed ..."
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
STOC '21: "Log-Rank and Lifting for AND-Functions ..."
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
STOC '21: "Support of Closed Walks and ..."
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
STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..."
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
STOC '21: "New Separations Results for ..."
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
STOC '21: "Algorithmic Foundations for ..."
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
STOC '21: "Settling the Robust Learnability ..."
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
STOC '21: "Learnability Can Be Independent ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Boosting Simple Learners ..."
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
STOC '21: "A Theory of Universal Learning ..."
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
STOC '21: "Structure vs. Randomness for ..."
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
STOC '21: "Robust Testing of Low Dimensional ..."
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
STOC '21: "Lower Bounds for Monotone ..."
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
STOC '21: "Distributed Weighted Min-Cut ..."
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
STOC '21: "Breaking the Quadratic Barrier ..."
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
STOC '21: "Simplicity Creates Inequity: ..."
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
STOC '21: "Graph Streaming Lower Bounds ..."
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
STOC '21: "Sparse Nonnegative Convolution ..."
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
STOC '21: "Distributed Weighted Min-Cut ..."
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
STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
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
STOC '21: "Breaking the Quadratic Barrier ..."
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
STOC '21: "A Framework for Quadratic ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Improving Schroeppel and Shamir’s ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "Robust Testing of Low Dimensional ..."
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
STOC '21: "Dynamic Planar Point Location ..."
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
STOC '21: "Combinatorial Bernoulli Factories: ..."
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
STOC '21: "Bipartite Perfect Matching ..."
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
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "A Deterministic Algorithm ..."
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
STOC '21: "Fiber Bundle Codes: Breaking ..."
Fiber Bundle Codes: Breaking the N1/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><sup>1/2</sup> 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
STOC '21: "Improved Quantum Data Analysis ..."
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
STOC '21: "Pseudodeterministic Algorithms ..."
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
STOC '21: "The Communication Complexity ..."
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
STOC '21: "Sample-Optimal and Efficient ..."
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
STOC '21: "Approximate Gomory–Hu Tree ..."
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
STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "Entropy Decay in the Swendsen–Wang ..."
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 ℤ<sup><i>d</i></sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1729-1728},
doi = {10.1145/3406325.3451095},
year = {2021},
}
Publisher's Version
STOC '21: "Cryptography from Sublinear-Time ..."
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
STOC '21: "Indistinguishability Obfuscation ..."
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
STOC '21: "Optimal Testing of Discrete ..."
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
STOC '21: "Polynomial Time Deterministic ..."
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 Σ<sup>[3]</sup>ΠΣΠ<sup>[2]</sup> 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
STOC '21: "Expander Random Walks: A Fourier-Analytic ..."
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
STOC '21: "Frozen 1-RSB Structure of ..."
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
STOC '21: "Information Theoretic Limits ..."
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
STOC '21: "Strong Co-nondeterministic ..."
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
STOC '21: "Finding Large Induced Sparse ..."
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<sub>>t</sub></i> -Free Graphs in Quasipolynomial Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {413-412},
doi = {10.1145/3406325.3451034},
year = {2021},
}
Publisher's Version
STOC '21: "Finding Large Induced Sparse ..."
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<sub>>t</sub></i> -Free Graphs in Quasipolynomial Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {413-412},
doi = {10.1145/3406325.3451034},
year = {2021},
}
Publisher's Version
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "Contextual Search in the Presence ..."
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
STOC '21: "Robust Linear Regression: ..."
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
STOC '21: "The Ghost in the Radiation: ..."
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
STOC '21: "Near-Optimal Learning of Tree-Structured ..."
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
STOC '21: "Optimal Testing of Discrete ..."
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
STOC '21: "Stronger Calibration Lower ..."
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
STOC '21: "Degree vs. Approximate Degree ..."
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
STOC '21: "Support of Closed Walks and ..."
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
STOC '21: "Continuous LWE ..."
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
STOC '21: "Efficient Two-Sided Markets ..."
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
STOC '21: "Outcome Indistinguishability ..."
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
STOC '21: "Eliminating Intermediate Measurements ..."
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
STOC '21: "A Polynomial-Time Approximation ..."
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
STOC '21: "When Is Approximate Counting ..."
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
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "A (2 + ε)-Approximation ..."
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
STOC '21: "The Communication Complexity ..."
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
STOC '21: "Efficient List-Decoding with ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "The Communication Complexity ..."
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
STOC '21: "Outcome Indistinguishability ..."
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
STOC '21: "Fiat–Shamir via List-Recoverable ..."
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
STOC '21: "Linear Bandits with Limited ..."
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
STOC '21: "Stronger Bounds for Weak Epsilon-Nets ..."
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
STOC '21: "The Randomized Communication ..."
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
STOC '21: "Exponential Communication ..."
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
STOC '21: "Settling the Complexity of ..."
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
STOC '21: "Finding Large Induced Sparse ..."
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<sub>>t</sub></i> -Free Graphs in Quasipolynomial Time},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {413-412},
doi = {10.1145/3406325.3451034},
year = {2021},
}
Publisher's Version
STOC '21: "Perfectly Sampling k ..."
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
STOC '21: "Indistinguishability Obfuscation ..."
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
STOC '21: "Hardness of Learning DNFs ..."
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
STOC '21: "On Codes Decoding a Constant ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "Strong Co-nondeterministic ..."
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
STOC '21: "Iterated Lower Bound Formulas: ..."
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
STOC '21: "Pseudodeterministic Algorithms ..."
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
STOC '21: "Reconstruction Algorithms ..."
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
STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "A New Coreset Framework for ..."
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
STOC '21: "The Complexity of Gradient ..."
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
STOC '21: "Perfectly Sampling k ..."
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
STOC '21: "Discrepancy Minimization via ..."
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
STOC '21: "Exponential Communication ..."
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
STOC '21: "Optimal Error Resilience of ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "On Codes Decoding a Constant ..."
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
STOC '21: "Contextual Search in the Presence ..."
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
STOC '21: "Combinatorial Bernoulli Factories: ..."
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
STOC '21: "Playing Unique Games on Certified ..."
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
STOC '21: "The Metric Relaxation for ..."
The Metric Relaxation for 0-Extension Admits an Ω(log2/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<sup>2/3</sup>k)</i> Gap},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1785-1784},
doi = {10.1145/3406325.3451071},
year = {2021},
}
Publisher's Version
STOC '21: "A New Coreset Framework for ..."
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
STOC '21: "Optimal Labelling Schemes ..."
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
STOC '21: "Load Balancing Guardrails: ..."
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
STOC '21: "Improved Dynamic Algorithms ..."
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
STOC '21: "Explicit Uniquely Decodable ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "A New Analysis of Differential ..."
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
STOC '21: "An Optimal Separation of Randomized ..."
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
STOC '21: "Fractionally Log-Concave and ..."
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
STOC '21: "Learnability Can Be Independent ..."
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
STOC '21: "Polynomial Time Deterministic ..."
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 Σ<sup>[3]</sup>ΠΣΠ<sup>[2]</sup> 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
STOC '21: "Online Stochastic Matching, ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "Explicit Uniquely Decodable ..."
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
STOC '21: "Entropy Decay in the Swendsen–Wang ..."
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 ℤ<sup><i>d</i></sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1729-1728},
doi = {10.1145/3406325.3451095},
year = {2021},
}
Publisher's Version
STOC '21: "k-Forrelation Optimally Separates ..."
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
STOC '21: "The Complexity of Constrained ..."
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
STOC '21: "When Is Memorization of Irrelevant ..."
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
STOC '21: "Automating Algebraic Proof ..."
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
STOC '21: "Continuous LWE ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "A Faster Algorithm for Solving ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "Support of Closed Walks and ..."
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
STOC '21: "Near-Linear Time Decoding ..."
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
STOC '21: "Playing Unique Games on Certified ..."
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
STOC '21: "An Optimal Separation of Randomized ..."
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
STOC '21: "Decoding Multivariate Multiplicity ..."
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
STOC '21: "Statistical Physics of Random ..."
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
STOC '21: "Degree vs. Approximate Degree ..."
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
STOC '21: "When Is Memorization of Irrelevant ..."
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
STOC '21: "The Ghost in the Radiation: ..."
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
STOC '21: "Continuous LWE ..."
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
STOC '21: "Chasing Convex Bodies with ..."
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
STOC '21: "Towards Tight Bounds for Spectral ..."
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
STOC '21: "Expander Random Walks: A Fourier-Analytic ..."
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
STOC '21: "Simple and Fast Derandomization ..."
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
STOC '21: "New Cosystolic Expanders from ..."
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(√n logk 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<sup><i>k</i></sup> <i>n</i>) Distance},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1477-1476},
doi = {10.1145/3406325.3451029},
year = {2021},
}
Publisher's Version
STOC '21: "Exponential Communication ..."
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
STOC '21: "Load Balancing with Dynamic ..."
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
STOC '21: "Efficient Randomized Distributed ..."
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
STOC '21: "Flow Time Scheduling with ..."
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
STOC '21: "Subcubic Algorithms for Gomory–Hu ..."
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
STOC '21: "Bridging the Gap between Tree ..."
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
STOC '21: "Near-Linear Time Decoding ..."
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
STOC '21: "The Metric Relaxation for ..."
The Metric Relaxation for 0-Extension Admits an Ω(log2/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<sup>2/3</sup>k)</i> Gap},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1785-1784},
doi = {10.1145/3406325.3451071},
year = {2021},
}
Publisher's Version
STOC '21: "Iterated Lower Bound Formulas: ..."
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
STOC '21: "Efficiently Learning Halfspaces ..."
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
STOC '21: "The Limits of Pan Privacy ..."
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
STOC '21: "Stronger Calibration Lower ..."
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
STOC '21: "Breaking the Quadratic Barrier ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "A Theory of Universal Learning ..."
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
STOC '21: "(Sub)Exponential Advantage ..."
(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
STOC '21: "Approximating Nash Social ..."
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
STOC '21: "Reducing Isotropy and Volume ..."
Reducing Isotropy and Volume to KLS: An O*(n3ψ2) 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><sup>3</sup><i>ψ</i><sup>2</sup>) Volume Algorithm},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1099-1098},
doi = {10.1145/3406325.3451018},
year = {2021},
}
Publisher's Version
STOC '21: "Optimal Mixing of Glauber ..."
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
STOC '21: "Entropy Decay in the Swendsen–Wang ..."
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 ℤ<sup><i>d</i></sup>},
booktitle = {Proc.\ STOC},
publisher = {ACM},
pages = {1729-1728},
doi = {10.1145/3406325.3451095},
year = {2021},
}
Publisher's Version
STOC '21: "Near-Optimal Learning of Tree-Structured ..."
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
STOC '21: "Log-Concave Polynomials in ..."
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
STOC '21: "Log-Concave Polynomials IV: ..."
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
STOC '21: "Greedy Adversarial Equilibrium: ..."
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
STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..."
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
STOC '21: "How Much Data Is Sufficient ..."
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
STOC '21: "Reconstruction Algorithms ..."
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
STOC '21: "Log-Concave Polynomials IV: ..."
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
STOC '21: "Fractionally Log-Concave and ..."
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
STOC '21: "Universally-Optimal Distributed ..."
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
STOC '21: "Minimum Cost Flows, MDPs, ..."
Minimum Cost Flows, MDPs, and ℓ1-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 ℓ<sub>1</sub>-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
STOC '21: "Information Theoretic Limits ..."
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
STOC '21: "A New Algorithm for Euclidean ..."
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
STOC '21: "Improving Schroeppel and Shamir’s ..."
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
STOC '21: "Tight Conditional Lower Bounds ..."
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
STOC '21: "Exponential Communication ..."
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
STOC '21: "A Faster Algorithm for Solving ..."
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
STOC '21: "A (2 + ε)-Approximation ..."
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
STOC '21: "Vertex Deletion Parameterized ..."
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
STOC '21: "Efficient Randomized DCAS ..."
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
STOC '21: "An Optimal Separation of Randomized ..."
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
STOC '21: "Frozen 1-RSB Structure of ..."
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
STOC '21: "Linear Bandits with Limited ..."
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
STOC '21: "A Nearly-Linear Time Algorithm ..."
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
STOC '21: "Learnability Can Be Independent ..."
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
STOC '21: "A Theory of Universal Learning ..."
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
STOC '21: "Sampling Constraint Satisfaction ..."
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
STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
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
STOC '21: "Adversarial Laws of Large ..."
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
STOC '21: "Outcome Indistinguishability ..."
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
STOC '21: "Towards Tight Bounds for Spectral ..."
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
STOC '21: "Almost Optimal Super-Constant-Pass ..."
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
STOC '21: "Log-Rank and Lifting for AND-Functions ..."
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
STOC '21: "The Complexity of Constrained ..."
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
STOC '21: "Efficiently Learning Halfspaces ..."
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
STOC '21: "Bridging the Gap between Tree ..."
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
STOC '21: "A Faster Algorithm for Solving ..."
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
STOC '21: "Succinct Blind Quantum Computation ..."
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
STOC '21: "SNARGs for Bounded Depth Computations ..."
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
STOC '21: "The Randomized Communication ..."
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
STOC '21: "Exponential Communication ..."
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
STOC '21: "Linear Bandits with Limited ..."
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
STOC '21: "Universally-Optimal Distributed ..."
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
STOC '21: "Hop-Constrained Oblivious ..."
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
STOC '21: "Tree Embeddings for Hop-Constrained ..."
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