default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID53rd STOC 2021: Virtual Event, Italy
- Samir Khuller, Virginia Vassilevska Williams:
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. ACM 2021, ISBN 978-1-4503-8053-9
Keynote
- Alfred V. Aho:
Computational thinking in programming language and compiler design (keynote). 1
Invited Talk
- Leonid A. Levin:
Climbing algorithms (invited talk). 2-3
Invited Papers
- Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros
:
A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper). 4 - C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang:
Chasing convex bodies with linear competitive ratio (invited paper). 5 - Arthur Jacot, Franck Gabriel, Clément Hongler:
Neural tangent kernel: convergence and generalization in neural networks (invited paper). 6 - Jon M. Kleinberg, Sendhil Mullainathan:
Simplicity creates inequity: implications for fairness, stereotypes, and interpretability (invited paper). 7 - Isaac H. Kim, Eugene Tang, John Preskill:
The ghost in the radiation: robust encodings of the black hole interior (invited paper). 8 - Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Moshe Shenfeld:
A new analysis of differential privacy's generalization guarantees (invited paper). 9 - Isaac Grosof, Ziv Scully, Mor Harchol-Balter:
Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper). 10 - Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Learnability can be independent of set theory (invited paper). 11
Tutorials
- Nima Anari, Cynthia Vinzant:
Log-concave polynomials in theory and applications (tutorial). 12 - Nike Sun:
Statistical physics of random CSPs (tutorial). 13
Best Student Papers
- Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney:
Discrepancy minimization via a self-balancing walk. 14-20 - Zachary Chase:
Separating words and trace reconstruction. 21-31
Best Papers
- Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
A (slightly) improved approximation algorithm for metric TSP. 32-45 - John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani:
The complexity of gradient descent: CLS = PPAD ∩ PLS. 46-59 - Aayush Jain, Huijia Lin, Amit Sahai:
Indistinguishability obfuscation from well-founded assumptions. 60-73
Session 1A
- Yufei Ruan, Jiaqi Yang, Yuan Zhou:
Linear bandits with limited adaptivity and learning distributional optimal design. 74-87 - Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Efficiently learning halfspaces with Tsybakov noise. 88-101 - Ainesh Bakshi, Adarsh Prasad:
Robust linear regression: optimal rates in polynomial time. 102-115 - Eddie Aamari, Alexander Knop:
Statistical query complexity of manifold estimation. 116-122 - Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar:
When is memorization of irrelevant training data necessary for high-accuracy learning? 123-132
Session 2A
- Constantinos Daskalakis, Qinxuan Pan:
Sample-optimal and efficient learning of tree Ising models. 133-146 - Arnab Bhattacharyya, Sutanu Gayen, Eric Price, N. V. Vinodchandran:
Near-optimal learning of tree-structured distributions by Chow-Liu. 147-160 - Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Anthimos Vardis Kandiros:
Learning Ising models from one or multiple samples. 161-168 - Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn:
A new coreset framework for clustering. 169-182 - Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi:
Sample-efficient proper PAC learning with approximate differential privacy. 183-196
Session 1B
- Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Log-rank and lifting for AND-functions. 197-208 - Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov:
Automating algebraic proof systems is NP-hard. 209-222 - Ján Pich, Rahul Santhanam:
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. 223-233 - Rahul Santhanam, Iddo Tzameret:
Iterated lower bound formulas: a diagonalization-based approach to proof complexity. 234-247 - Mark Braverman, Dor Minzer:
New separations results for external information. 248-258
Session 2B
- Shir Peleg, Amir Shpilka:
Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials. 259-271 - Zander Kelley:
An improved derandomization of the switching lemma. 272-282 - Lijie Chen, Roei Tell:
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. 283-291 - Shuichi Hirahara:
Average-case hardness of NP from exponential worst-case hardness assumptions. 292-302 - Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam:
Pseudodeterministic algorithms and the structure of probabilistic time. 303-316
Session 1C
- Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai:
Vertex connectivity in poly-logarithmic max-flows. 317-329 - Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time. 330-341 - Arnold Filtser, Hung Le:
Clan embeddings into trees, and low treewidth graphs. 342-355 - Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic:
Tree embeddings for hop-constrained network design. 356-369 - Federica Cecchetto, Vera Traub, Rico Zenklusen:
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. 370-383
Session 2C
- Jason Li:
Deterministic mincut in almost-linear time. 384-395 - Theo McKenzie, Peter Michael Reichstein Rasmussen, Nikhil Srivastava:
Support of closed walks and second eigenvalue multiplicity of graphs. 396-407 - Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong:
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. 408-420 - Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai:
Breaking the quadratic barrier for matroid intersection. 421-432 - Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong:
Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. 433-446
Session 3A
- Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev:
Adversarial laws of large numbers and optimal regret in online classification. 447-455 - Mingda Qiao, Gregory Valiant:
Stronger calibration lower bounds via sidestepping. 456-466 - Suprovat Ghoshal, Rishi Saket:
Hardness of learning DNFs using halfspaces. 467-480 - Noga Alon, Alon Gonen, Elad Hazan, Shay Moran:
Boosting simple learners. 481-489 - Sitan Chen, Ankur Moitra:
Algorithmic foundations for the diffraction limit. 490-503
Session 4A
- Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms:
VC dimension and distribution-free sample-based testing. 504-517 - Allen Liu, Ankur Moitra:
Settling the robust learnability of mixtures of Gaussians. 518-531 - Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir Yehudayoff:
A theory of universal learning. 532-541 - Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price:
Optimal testing of discrete distributions with high probability. 542-555
Session 3B
- Seth Pettie, Dingyu Wang:
Information theoretic limits of cardinality estimation: Fisher meets Shannon. 556-569 - Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu:
Almost optimal super-constant-pass streaming lower bounds for reachability. 570-583 - Anindya De, Elchanan Mossel, Joe Neeman:
Robust testing of low dimensional functions. 584-597 - Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida:
Towards tight bounds for spectral sparsification of hypergraphs. 598-611 - Sepehr Assadi, Vishvajeet N:
Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. 612-625
Session 4B
- Julia Chuzhoy:
Decremental all-pairs shortest paths in deterministic near-linear time. 626-639 - Tomasz Kociumaka, Saeed Seddighin:
Improved dynamic algorithms for longest increasing subsequence. 640-653 - Pawel Gawrychowski, Wojciech Janczewski:
Fully dynamic approximation of LIS in polylogarithmic time. 654-667 - Aaron Bernstein, Aditi Dudeja, Zachary Langley:
A framework for dynamic matching in weighted graphs. 668-681 - Zhiyi Huang, Xinkai Shu:
Online stochastic matching, poisson arrivals, and the natural linear program. 682-693
Session 3C
- Joan Bruna, Oded Regev, Min Jae Song, Yi Tang:
Continuous LWE. 694-707 - Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang:
SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. 708-721 - Yanyi Liu, Rafael Pass:
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity. 722-735 - Romain Gay, Rafael Pass:
Indistinguishability obfuscation from circular security. 736-749 - Justin Holmgren, Alex Lombardi, Ron D. Rothblum:
Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). 750-760
Session 4C
- Lijie Chen, Xin Lyu:
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. 761-771 - Josh Alman:
Kronecker products, low-depth circuits, and matrix rigidity. 772-785 - Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay:
Lower bounds for monotone arithmetic circuits via communication complexity. 786-799 - Alex Cohen, Guy Moshkovitz:
Structure vs. randomness for bilinear maps. 800-808 - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. 809-822
Session 5A
- Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang:
A faster algorithm for solving general LPs. 823-832 - Rad Niazadeh, Renato Paes Leme, Jon Schneider:
Combinatorial Bernoulli factories: matchings, flows, and other polytopes. 833-846 - Leonid Gurvits, Jonathan Leake:
Capacity lower bounds via productization. 847-858 - 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. 859-869 - Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor:
A framework for quadratic form maximization over convex sets through nonconvex relaxations. 870-881
Session 5B
- Aviad Rubinstein, Junyao Zhao:
The randomized communication complexity of randomized auctions. 882-895 - Oren Mangoubi, Nisheeth K. Vishnoi:
Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization. 896-909 - Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert E. Schapire:
Contextual search in the presence of irrational agents. 910-918 - 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. 919-932 - Shahar Dobzinski, Shiri Ron:
The communication complexity of payment computation. 933-946 - Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao:
Exponential communication separations between notions of selfishness. 947-960
Session 5C
- He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala:
Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm. 961-974 - Haitao Wang:
A new algorithm for Euclidean shortest paths in the plane. 975-988 - Natan Rubin:
Stronger bounds for weak epsilon-nets in higher dimensions. 989-1002 - Yakov Nekrich:
Dynamic planar point location in optimal time. 1003-1014
Session 6A
- Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros:
When is approximate counting for conjunctive queries tractable? 1015-1027 - Yair Bartal, Lee-Ad Gottlieb:
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. 1028-1041 - Lars Rohwedder, Andreas Wiese:
A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine. 1042-1055 - Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A quasipolynomial (2 + ε)-approximation for planar sparsest cut. 1056-1069 - Yossi Azar, Stefano Leonardi, Noam Touitou:
Flow time scheduling with uncertain processing time. 1070-1080
Session 7A
- Albert Cheu, Jonathan R. Ullman:
The limits of pan privacy and shuffle privacy for learning and estimation. 1081-1094 - Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona:
Outcome indistinguishability. 1095-1108 - Marthe Bonamy, Louis Esperet, Carla Groenland, Alex D. Scott:
Optimal labelling schemes for adjacency, comparability, and reachability. 1109-1117 - Gal Beniamini, Noam Nisan:
Bipartite perfect matching as a real polynomial. 1118-1131 - Marco Bressan:
Efficient and near-optimal algorithms for sampling connected subgraphs. 1132-1143
Session 6B
- Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai:
Distributed weighted min-cut in nearly-optimal time. 1144-1153 - Krzysztof Nowicki:
A deterministic algorithm for the MST problem in constant rounds of congested clique. 1154-1165 - Bernhard Haeupler, David Wajc, Goran Zuzic:
Universally-optimal distributed algorithms for known topologies. 1166-1179 - Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan:
Efficient randomized distributed coloring in CONGEST. 1180-1193 - Nachum Dershowitz, Rotem Oshman, Tal Roth:
The communication complexity of multiparty set disjointness under product distributions. 1194-1207
Session 7B
- Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic:
Hop-constrained oblivious routing. 1208-1220 - George Giakkoupis, Mehrdad Jafari Giv, Philipp Woelfel:
Efficient randomized DCAS. 1221-1234 - Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena:
Optimal error resilience of adaptive message exchange. 1235-1247 - William Kuszmaul:
How asymmetry helps buffer management: achieving optimal tail size in cup games. 1248-1261 - Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup:
Load balancing with dynamic set of balls and bins. 1262-1275
Session 6C
- Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell:
Fiber bundle codes: breaking the n1/2 polylog(n) barrier for Quantum LDPC codes. 1276-1288 - Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An optimal separation of randomized and Quantum query complexity. 1289-1302 - Nikhil Bansal, Makrand Sinha:
k-forrelation optimally separates Quantum and classical query complexity. 1303-1316 - Tali Kaufman, Ran J. Tessler:
New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√n logk n) distance. 1317-1329 - Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal:
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. 1330-1342 - Bill Fefferman, Zachary Remscrim:
Eliminating intermediate measurements in space-bounded Quantum computation. 1343-1356
Session 7C
- András Gilyén, Matthew B. Hastings, Umesh V. Vazirani:
(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. 1357-1369 - Jiayu Zhang:
Succinct blind Quantum computation using a random oracle. 1370-1383 - Jonathan Leake, Colin S. McSwiggen, Nisheeth K. Vishnoi:
Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and differential privacy. 1384-1397 - Costin Badescu, Ryan O'Donnell:
Improved Quantum data analysis. 1398-1411
Session 8A
- Jugal Garg, Edin Husic, László A. Végh:
Approximating Nash social welfare under rado valuations. 1412-1425 - Yakov Babichenko, Aviad Rubinstein:
Settling the complexity of Nash equilibrium in congestion games. 1426-1437 - Yiding Feng, Jason D. Hartline, Yingkai Li:
Revelation gap for pricing from samples. 1438-1451 - Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser:
Efficient two-sided markets with limited information. 1452-1465 - Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis:
The complexity of constrained min-max optimization. 1466-1478
Session 9A
- Jan Hazla, Alex Samorodnitsky, Ori Sberlo:
On codes decoding a constant fraction of errors on the BSC. 1479-1488 - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding multivariate multiplicity codes on product sets. 1489-1501 - Zeyu Guo, Noga Ron-Zewi:
Efficient list-decoding with constant alphabet and list sizes. 1502-1515 - Ronen Shaltiel, Jad Silbak:
Explicit uniquely decodable codes for space bounded channels that achieve list-decoding capacity. 1516-1526 - Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
Near-linear time decoding of Ta-Shma's codes via splittable regularity. 1527-1536
Session 8B
- Zongchen Chen, Kuikui Liu, Eric Vigoda:
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. 1537-1550 - Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda:
Entropy decay in the Swendsen-Wang dynamics on ℤd. 1551-1564 - Weiming Feng, Kun He, Yitong Yin:
Sampling constraint satisfaction solutions in the local lemma regime. 1565-1578 - Will Perkins, Changji Xu:
Frozen 1-RSB structure of the symmetric Ising perceptron. 1579-1588 - Vishesh Jain, Ashwin Sah, Mehtaab Sawhney:
Perfectly sampling k ≥ (8/3 + o(1))Δ-colorings in graphs. 1589-1600
Session 9B
- Roy Schwartz, Nitzan Tur:
The metric relaxation for 0-extension admits an Ω(log2/3k) gap. 1601-1614 - Amey Bhangale, Subhash Khot:
Optimal inapproximability of satisfiable k-LIN over non-abelian groups. 1615-1628 - Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer:
Playing unique games on certified small-set expanders. 1629-1642 - Gil Cohen, Noam Peri, Amnon Ta-Shma:
Expander random walks: a Fourier-analytic approach. 1643-1655 - Nathan Keller, Ohad Klein:
Local concentration inequalities and Tomaszewski's conjecture. 1656-1669
Session 8C
- Jesper Nederlof, Karol Wegrzycki:
Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. 1670-1683 - Ray Li:
Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH). 1684-1696 - Mina Dalirrooyfard, Nicole Wein:
Tight conditional lower bounds for approximating diameter in directed graphs. 1697-1710 - Karl Bringmann, Nick Fischer, Vasileios Nakos:
Sparse nonnegative convolution is equivalent to dense nonnegative convolution. 1711-1724 - Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. 1725-1737 - Jason Li, Debmalya Panigrahi:
Approximate Gomory-Hu tree is faster than n - 1 max-flows. 1738-1748
Session 9C
- Bingkai Lin:
Constant approximating k-clique is w[1]-hard. 1749-1756 - Bart M. P. Jansen, Jari J. H. de Kroon, Michal Wlodarczyk:
Vertex deletion parameterized by elimination distance and even less. 1757-1769 - Radu Curticapean:
A full complexity dichotomy for immanant families. 1770-1783 - Sally Dong, Yin Tat Lee, Guanghao Ye:
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. 1784-1797
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-04 01:26 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
