- Maria-Florina Balcan, Dan F. DeBlasio
, Travis Dick, Carl Kingsford, Tuomas Sandholm, Ellen Vitercik:
How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. STOC 2021: 919-932 - Nikhil Bansal, Makrand Sinha:
k-forrelation optimally separates Quantum and classical query complexity. STOC 2021: 1303-1316 - Yair Bartal, Lee-Ad Gottlieb:
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. STOC 2021: 1028-1041 - Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Learnability can be independent of set theory (invited paper). STOC 2021: 11 - Gal Beniamini, Noam Nisan:
Bipartite perfect matching as a real polynomial. STOC 2021: 1118-1131 - Aaron Bernstein, Aditi Dudeja, Zachary Langley:
A framework for dynamic matching in weighted graphs. STOC 2021: 668-681 - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding multivariate multiplicity codes on product sets. STOC 2021: 1489-1501 - Amey Bhangale, Subhash Khot:
Optimal inapproximability of satisfiable k-LIN over non-abelian groups. STOC 2021: 1615-1628 - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. STOC 2021: 809-822 - Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor:
A framework for quadratic form maximization over convex sets through nonconvex relaxations. STOC 2021: 870-881 - Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms:
VC dimension and distribution-free sample-based testing. STOC 2021: 504-517 - Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda:
Entropy decay in the Swendsen-Wang dynamics on ℤd. STOC 2021: 1551-1564 - Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai:
Breaking the quadratic barrier for matroid intersection. STOC 2021: 421-432 - Marthe Bonamy, Louis Esperet, Carla Groenland, Alex D. Scott:
Optimal labelling schemes for adjacency, comparability, and reachability. STOC 2021: 1109-1117 - Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff:
A theory of universal learning. STOC 2021: 532-541 - Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang:
Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances. STOC 2021: 859-869 - Mark Braverman, Dor Minzer:
New separations results for external information. STOC 2021: 248-258 - Karl Bringmann, Nick Fischer, Vasileios Nakos:
Sparse nonnegative convolution is equivalent to dense nonnegative convolution. STOC 2021: 1711-1724 - Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar:
When is memorization of irrelevant training data necessary for high-accuracy learning? STOC 2021: 123-132 - Joan Bruna, Oded Regev, Min Jae Song, Yi Tang:
Continuous LWE. STOC 2021: 694-707 - Federica Cecchetto, Vera Traub, Rico Zenklusen:
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. STOC 2021: 370-383 - Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay:
Lower bounds for monotone arithmetic circuits via communication complexity. STOC 2021: 786-799 - Zongchen Chen, Kuikui Liu, Eric Vigoda:
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. STOC 2021: 1537-1550 - Sitan Chen, Ankur Moitra:
Algorithmic foundations for the diffraction limit. STOC 2021: 490-503 - Albert Cheu, Jonathan R. Ullman:
The limits of pan privacy and shuffle privacy for learning and estimation. STOC 2021: 1081-1094 - Julia Chuzhoy:
Decremental all-pairs shortest paths in deterministic near-linear time. STOC 2021: 626-639 - Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A quasipolynomial (2 + ε)-approximation for planar sparsest cut. STOC 2021: 1056-1069 - Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
A new coreset framework for clustering. STOC 2021: 169-182 - Alex Cohen, Guy Moshkovitz:
Structure vs. randomness for bilinear maps. STOC 2021: 800-808 - Gil Cohen, Noam Peri, Amnon Ta-Shma:
Expander random walks: a Fourier-analytic approach. STOC 2021: 1643-1655
