STOC 2021
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)
Powered by
Conference Publishing Consulting

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), June 21–25, 2021, Virtual, Italy

STOC 2021 – Author Index

Contents - Abstracts - Authors

A B C D E F G H J K L M N O P Q R S T U V W X Y Z

Aamand, Anders STOC '21: "Load Balancing with Dynamic ..." Article: stoc21main-p394-p (type: Full Paper) doi:10.1145/3406325.3451107
Aamari, Eddie STOC '21: "Statistical Query Complexity ..." Article: stoc21main-p11-p (type: Full Paper) doi:10.1145/3406325.3451135
Aaronson, Scott STOC '21: "Degree vs. Approximate Degree ..." Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047
Abboud, Amir STOC '21: "Subcubic Algorithms for Gomory–Hu ..." Article: stoc21main-p262-p (type: Full Paper) doi:10.1145/3406325.3451073
Aho, Alfred V. STOC '21: "Computational Thinking in ..." Article: stoc21invited-inv2-p (type: Abstract (1 page)) doi:10.1145/3406325.3465350
Alimohammadi, Yeganeh STOC '21: "Fractionally Log-Concave and ..." Article: stoc21main-p456-p (type: Full Paper) doi:10.1145/3406325.3451123
Alman, Josh STOC '21: "Kronecker Products, Low-Depth ..." Article: stoc21main-p43-p (type: Full Paper) doi:10.1145/3406325.3451008
Alon, Noga STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041 STOC '21: "Boosting Simple Learners ..." Article: stoc21main-p105-p (type: Full Paper) doi:10.1145/3406325.3451030
Alweiss, Ryan STOC '21: "Discrepancy Minimization via ..." Article: stoc21main-p2-p (type: Full Paper) doi:10.1145/3406325.3450994
Anari, Nima STOC '21: "Log-Concave Polynomials in ..." Article: stoc21invited-inv3-p (type: Abstract (1 page)) doi:10.1145/3406325.3465351 STOC '21: "Log-Concave Polynomials IV: ..." Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091 STOC '21: "Fractionally Log-Concave and ..." Article: stoc21main-p456-p (type: Full Paper) doi:10.1145/3406325.3451123
Arenas, Marcelo STOC '21: "A Polynomial-Time Approximation ..." Article: stoc21invited-inv5-p (type: Abstract (1 page)) doi:10.1145/3406325.3465353 STOC '21: "When Is Approximate Counting ..." Article: stoc21main-p60-p (type: Full Paper) doi:10.1145/3406325.3451014
Argue, C. J. STOC '21: "Chasing Convex Bodies with ..." Article: stoc21invited-inv6-p (type: Abstract (1 page)) doi:10.1145/3406325.3465354
Assadi, Sepehr STOC '21: "Graph Streaming Lower Bounds ..." Article: stoc21main-p408-p (type: Full Paper) doi:10.1145/3406325.3451110
Azar, Yossi STOC '21: "Flow Time Scheduling with ..." Article: stoc21main-p83-p (type: Full Paper) doi:10.1145/3406325.3451023
Babichenko, Yakov STOC '21: "Settling the Complexity of ..." Article: stoc21main-p132-p (type: Full Paper) doi:10.1145/3406325.3451039
Bădescu, Costin STOC '21: "Improved Quantum Data Analysis ..." Article: stoc21main-p404-p (type: Full Paper) doi:10.1145/3406325.3451109
Bafna, Mitali STOC '21: "Playing Unique Games on Certified ..." Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099
Bakshi, Ainesh STOC '21: "Robust Linear Regression: ..." Article: stoc21main-p26-p (type: Full Paper) doi:10.1145/3406325.3451001
Balcan, Maria-Florina STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
Bansal, Nikhil STOC '21: "k-Forrelation Optimally Separates ..." Article: stoc21main-p141-p (type: Full Paper) doi:10.1145/3406325.3451040
Barak, Boaz STOC '21: "Playing Unique Games on Certified ..." Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099
Bartal, Yair STOC '21: "Near-Linear Time Approximation ..." Article: stoc21main-p210-p (type: Full Paper) doi:10.1145/3406325.3451063
Ben-David, Shai STOC '21: "Learnability Can Be Independent ..." Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360
Ben-David, Shalev STOC '21: "Degree vs. Approximate Degree ..." Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047
Ben-Eliezer, Omri STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041
Beniamini, Gal STOC '21: "Bipartite Perfect Matching ..." Article: stoc21main-p27-p (type: Full Paper) doi:10.1145/3406325.3451002
Bernstein, Aaron STOC '21: "A Framework for Dynamic Matching ..." Article: stoc21main-p418-p (type: Full Paper) doi:10.1145/3406325.3451113
Bhandari, Siddharth STOC '21: "Decoding Multivariate Multiplicity ..." Article: stoc21main-p97-p (type: Full Paper) doi:10.1145/3406325.3451027
Bhangale, Amey STOC '21: "Optimal Inapproximability ..." Article: stoc21main-p29-p (type: Full Paper) doi:10.1145/3406325.3451003
Bhargava, Vishwas STOC '21: "Reconstruction Algorithms ..." Article: stoc21main-p336-p (type: Full Paper) doi:10.1145/3406325.3451096
Bhattacharyya, Arnab STOC '21: "Near-Optimal Learning of Tree-Structured ..." Article: stoc21main-p217-p (type: Full Paper) doi:10.1145/3406325.3451066
Bhattiprolu, Vijay STOC '21: "A Framework for Quadratic ..." Article: stoc21main-p483-p (type: Full Paper) doi:10.1145/3406325.3451128
Blais, Eric STOC '21: "VC Dimension and Distribution-Free ..." Article: stoc21main-p380-p (type: Full Paper) doi:10.1145/3406325.3451104
Blanca, Antonio STOC '21: "Entropy Decay in the Swendsen–Wang ..." Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095
Blikstad, Joakim STOC '21: "Breaking the Quadratic Barrier ..." Article: stoc21main-p325-p (type: Full Paper) doi:10.1145/3406325.3451092
Bonamy, Marthe STOC '21: "Optimal Labelling Schemes ..." Article: stoc21main-p374-p (type: Full Paper) doi:10.1145/3406325.3451102
Bousquet, Olivier STOC '21: "A Theory of Universal Learning ..." Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087
Braverman, Mark STOC '21: "New Separations Results for ..." Article: stoc21main-p154-p (type: Full Paper) doi:10.1145/3406325.3451044
Bressan, Marco STOC '21: "Efficient and Near-Optimal ..." Article: stoc21main-p147-p (type: Full Paper) doi:10.1145/3406325.3451042
Bringmann, Karl STOC '21: "Sparse Nonnegative Convolution ..." Article: stoc21main-p318-p (type: Full Paper) doi:10.1145/3406325.3451090
Brown, Gavin STOC '21: "When Is Memorization of Irrelevant ..." Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131
Bruna, Joan STOC '21: "Continuous LWE ..." Article: stoc21main-p24-p (type: Full Paper) doi:10.1145/3406325.3451000
Bun, Mark STOC '21: "When Is Memorization of Irrelevant ..." Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131
Caputo, Pietro STOC '21: "Entropy Decay in the Swendsen–Wang ..." Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095
Cecchetto, Federica STOC '21: "Bridging the Gap between Tree ..." Article: stoc21main-p308-p (type: Full Paper) doi:10.1145/3406325.3451086
Chase, Zachary STOC '21: "Separating Words and Trace ..." Article: stoc21main-p443-p (type: Full Paper) doi:10.1145/3406325.3451118
Chattopadhyay, Arkadev STOC '21: "Lower Bounds for Monotone ..." Article: stoc21main-p241-p (type: Full Paper) doi:10.1145/3406325.3451069
Chen, Lijie STOC '21: "Simple and Fast Derandomization ..." Article: stoc21main-p192-p (type: Full Paper) doi:10.1145/3406325.3451059 STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038 STOC '21: "Inverse-Exponential Correlation ..." Article: stoc21main-p491-p (type: Full Paper) doi:10.1145/3406325.3451132
Chen, Sitan STOC '21: "Algorithmic Foundations for ..." Article: stoc21main-p276-p (type: Full Paper) doi:10.1145/3406325.3451078
Chen, Zongchen STOC '21: "Optimal Mixing of Glauber ..." Article: stoc21main-p121-p (type: Full Paper) doi:10.1145/3406325.3451035
Cheu, Albert STOC '21: "The Limits of Pan Privacy ..." Article: stoc21main-p3-p (type: Full Paper) doi:10.1145/3406325.3450995
Chuzhoy, Julia STOC '21: "Decremental All-Pairs Shortest ..." Article: stoc21main-p94-p (type: Full Paper) doi:10.1145/3406325.3451025
Cohen, Alex STOC '21: "Structure vs. Randomness for ..." Article: stoc21main-p41-p (type: Full Paper) doi:10.1145/3406325.3451007
Cohen, Gil STOC '21: "Expander Random Walks: A Fourier-Analytic ..." Article: stoc21main-p168-p (type: Full Paper) doi:10.1145/3406325.3451049
Cohen-Addad, Vincent STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." Article: stoc21main-p379-p (type: Full Paper) doi:10.1145/3406325.3451103 STOC '21: "A New Coreset Framework for ..." Article: stoc21main-p81-p (type: Full Paper) doi:10.1145/3406325.3451022
Croquevielle, Luis Alberto STOC '21: "A Polynomial-Time Approximation ..." Article: stoc21invited-inv5-p (type: Abstract (1 page)) doi:10.1145/3406325.3465353 STOC '21: "When Is Approximate Counting ..." Article: stoc21main-p60-p (type: Full Paper) doi:10.1145/3406325.3451014
Curticapean, Radu STOC '21: "A Full Complexity Dichotomy ..." Article: stoc21main-p467-p (type: Full Paper) doi:10.1145/3406325.3451124
Dagan, Yuval STOC '21: "Learning Ising Models from ..." Article: stoc21main-p266-p (type: Full Paper) doi:10.1145/3406325.3451074 STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041
Dalirrooyfard, Mina STOC '21: "Tight Conditional Lower Bounds ..." Article: stoc21main-p489-p (type: Full Paper) doi:10.1145/3406325.3451130
Daskalakis, Constantinos STOC '21: "The Complexity of Constrained ..." Article: stoc21main-p470-p (type: Full Paper) doi:10.1145/3406325.3451125 STOC '21: "Sample-Optimal and Efficient ..." Article: stoc21main-p39-p (type: Full Paper) doi:10.1145/3406325.3451006 STOC '21: "Learning Ising Models from ..." Article: stoc21main-p266-p (type: Full Paper) doi:10.1145/3406325.3451074
Datta, Rajit STOC '21: "Lower Bounds for Monotone ..." Article: stoc21main-p241-p (type: Full Paper) doi:10.1145/3406325.3451069
De, Anindya STOC '21: "Robust Testing of Low Dimensional ..." Article: stoc21main-p421-p (type: Full Paper) doi:10.1145/3406325.3451115
DeBlasio, Dan STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
De Kroon, Jari J. H. STOC '21: "Vertex Deletion Parameterized ..." Article: stoc21main-p239-p (type: Full Paper) doi:10.1145/3406325.3451068
De Rezende, Susanna F. STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Dershowitz, Nachum STOC '21: "The Communication Complexity ..." Article: stoc21main-p386-p (type: Full Paper) doi:10.1145/3406325.3451106
Diakonikolas, Ilias STOC '21: "Efficiently Learning Halfspaces ..." Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998 STOC '21: "Optimal Testing of Discrete ..." Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997
Dick, Travis STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
Dikkala, Nishanth STOC '21: "Learning Ising Models from ..." Article: stoc21main-p266-p (type: Full Paper) doi:10.1145/3406325.3451074
Dobzinski, Shahar STOC '21: "The Communication Complexity ..." Article: stoc21main-p303-p (type: Full Paper) doi:10.1145/3406325.3451083
Dong, Sally STOC '21: "A Nearly-Linear Time Algorithm ..." Article: stoc21main-p185-p (type: Full Paper) doi:10.1145/3406325.3451056
Dory, Michal STOC '21: "Distributed Weighted Min-Cut ..." Article: stoc21main-p77-p (type: Full Paper) doi:10.1145/3406325.3451020
Dudeja, Aditi STOC '21: "A Framework for Dynamic Matching ..." Article: stoc21main-p418-p (type: Full Paper) doi:10.1145/3406325.3451113
Dütting, Paul STOC '21: "Efficient Two-Sided Markets ..." Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076
Dwork, Cynthia STOC '21: "Outcome Indistinguishability ..." Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064
Efremenko, Klim STOC '21: "Optimal Error Resilience of ..." Article: stoc21main-p273-p (type: Full Paper) doi:10.1145/3406325.3451077
Efron, Yuval STOC '21: "Distributed Weighted Min-Cut ..." Article: stoc21main-p77-p (type: Full Paper) doi:10.1145/3406325.3451020
Esperet, Louis STOC '21: "Optimal Labelling Schemes ..." Article: stoc21main-p374-p (type: Full Paper) doi:10.1145/3406325.3451102
Fearnley, John STOC '21: "The Complexity of Gradient ..." Article: stoc21main-p173-p (type: Full Paper) doi:10.1145/3406325.3451052
Fefferman, Bill STOC '21: "Eliminating Intermediate Measurements ..." Article: stoc21main-p171-p (type: Full Paper) doi:10.1145/3406325.3451051
Feldman, Vitaly STOC '21: "When Is Memorization of Irrelevant ..." Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131
Feng, Weiming STOC '21: "Sampling Constraint Satisfaction ..." Article: stoc21main-p369-p (type: Full Paper) doi:10.1145/3406325.3451101
Feng, Yiding STOC '21: "Revelation Gap for Pricing ..." Article: stoc21main-p189-p (type: Full Paper) doi:10.1145/3406325.3451057
Ferreira Pinto Jr., Renato STOC '21: "VC Dimension and Distribution-Free ..." Article: stoc21main-p380-p (type: Full Paper) doi:10.1145/3406325.3451104
Filtser, Arnold STOC '21: "Clan Embeddings into Trees, ..." Article: stoc21main-p148-p (type: Full Paper) doi:10.1145/3406325.3451043
Fischer, Nick STOC '21: "Sparse Nonnegative Convolution ..." Article: stoc21main-p318-p (type: Full Paper) doi:10.1145/3406325.3451090
Fusco, Federico STOC '21: "Efficient Two-Sided Markets ..." Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076
Gabriel, Franck STOC '21: "Neural Tangent Kernel: Convergence ..." Article: stoc21invited-inv7-p (type: Abstract (1 page)) doi:10.1145/3406325.3465355
Garg, Jugal STOC '21: "Approximating Nash Social ..." Article: stoc21main-p113-p (type: Full Paper) doi:10.1145/3406325.3451031
Gartland, Peter STOC '21: "Finding Large Induced Sparse ..." Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034
Gawrychowski, Paweł STOC '21: "Fully Dynamic Approximation ..." Article: stoc21main-p455-p (type: Full Paper) doi:10.1145/3406325.3451137
Gay, Romain STOC '21: "Indistinguishability Obfuscation ..." Article: stoc21main-p242-p (type: Full Paper) doi:10.1145/3406325.3451070
Gayen, Sutanu STOC '21: "Near-Optimal Learning of Tree-Structured ..." Article: stoc21main-p217-p (type: Full Paper) doi:10.1145/3406325.3451066
Ghaffari, Mohsen STOC '21: "Hop-Constrained Oblivious ..." Article: stoc21main-p344-p (type: Full Paper) doi:10.1145/3406325.3451098
Gharan, Shayan Oveis STOC '21: "Log-Concave Polynomials IV: ..." Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091 STOC '21: "A (Slightly) Improved Approximation ..." Article: stoc21main-p49-p (type: Full Paper) doi:10.1145/3406325.3451009
Ghazi, Badih STOC '21: "Sample-Efficient Proper PAC ..." Article: stoc21main-p98-p (type: Full Paper) doi:10.1145/3406325.3451028
Ghoshal, Suprovat STOC '21: "Hardness of Learning DNFs ..." Article: stoc21main-p228-p (type: Full Paper) doi:10.1145/3406325.3451067
Giakkoupis, George STOC '21: "Efficient Randomized DCAS ..." Article: stoc21main-p497-p (type: Full Paper) doi:10.1145/3406325.3451133
Gilyén, András STOC '21: "(Sub)Exponential Advantage ..." Article: stoc21main-p194+p370-p (type: Full Paper) doi:10.1145/3406325.3451060
Giv, Mehrdad Jafari STOC '21: "Efficient Randomized DCAS ..." Article: stoc21main-p497-p (type: Full Paper) doi:10.1145/3406325.3451133
Goldberg, Paul W. STOC '21: "The Complexity of Gradient ..." Article: stoc21main-p173-p (type: Full Paper) doi:10.1145/3406325.3451052
Golowich, Noah STOC '21: "Sample-Efficient Proper PAC ..." Article: stoc21main-p98-p (type: Full Paper) doi:10.1145/3406325.3451028
Gonen, Alon STOC '21: "Boosting Simple Learners ..." Article: stoc21main-p105-p (type: Full Paper) doi:10.1145/3406325.3451030
Göös, Mika STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Gottlieb, Lee-Ad STOC '21: "Near-Linear Time Approximation ..." Article: stoc21main-p210-p (type: Full Paper) doi:10.1145/3406325.3451063
Gouleakis, Themis STOC '21: "Optimal Testing of Discrete ..." Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997
Groenland, Carla STOC '21: "Optimal Labelling Schemes ..." Article: stoc21main-p374-p (type: Full Paper) doi:10.1145/3406325.3451102
Grosof, Isaac STOC '21: "Load Balancing Guardrails: ..." Article: stoc21invited-inv11-p (type: Abstract (1 page)) doi:10.1145/3406325.3465359
Guo, Zeyu STOC '21: "Efficient List-Decoding with ..." Article: stoc21main-p156-p (type: Full Paper) doi:10.1145/3406325.3451046
Gupta, Anupam STOC '21: "Chasing Convex Bodies with ..." Article: stoc21invited-inv6-p (type: Abstract (1 page)) doi:10.1145/3406325.3465354 STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." Article: stoc21main-p379-p (type: Full Paper) doi:10.1145/3406325.3451103
Guruganesh, Guru STOC '21: "Chasing Convex Bodies with ..." Article: stoc21invited-inv6-p (type: Abstract (1 page)) doi:10.1145/3406325.3465354
Gurvits, Leonid STOC '21: "Capacity Lower Bounds via ..." Article: stoc21main-p381-p (type: Full Paper) doi:10.1145/3406325.3451105
Haah, Jeongwan STOC '21: "Fiber Bundle Codes: Breaking ..." Article: stoc21main-p32-p (type: Full Paper) doi:10.1145/3406325.3451005
Haeupler, Bernhard STOC '21: "Universally-Optimal Distributed ..." Article: stoc21main-p285-p (type: Full Paper) doi:10.1145/3406325.3451081 STOC '21: "Hop-Constrained Oblivious ..." Article: stoc21main-p344-p (type: Full Paper) doi:10.1145/3406325.3451098 STOC '21: "Tree Embeddings for Hop-Constrained ..." Article: stoc21main-p175-p (type: Full Paper) doi:10.1145/3406325.3451053
Halldórsson, Magnús M. STOC '21: "Efficient Randomized Distributed ..." Article: stoc21main-p317-p (type: Full Paper) doi:10.1145/3406325.3451089
Hanneke, Steve STOC '21: "A Theory of Universal Learning ..." Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087
Harchol-Balter, Mor STOC '21: "Load Balancing Guardrails: ..." Article: stoc21invited-inv11-p (type: Abstract (1 page)) doi:10.1145/3406325.3465359
Harms, Nathaniel STOC '21: "VC Dimension and Distribution-Free ..." Article: stoc21main-p380-p (type: Full Paper) doi:10.1145/3406325.3451104
Harsha, Prahladh STOC '21: "Decoding Multivariate Multiplicity ..." Article: stoc21main-p97-p (type: Full Paper) doi:10.1145/3406325.3451027
Hartline, Jason D. STOC '21: "Revelation Gap for Pricing ..." Article: stoc21main-p189-p (type: Full Paper) doi:10.1145/3406325.3451057
Hastings, Matthew B. STOC '21: "Fiber Bundle Codes: Breaking ..." Article: stoc21main-p32-p (type: Full Paper) doi:10.1145/3406325.3451005 STOC '21: "(Sub)Exponential Advantage ..." Article: stoc21main-p194+p370-p (type: Full Paper) doi:10.1145/3406325.3451060
Hazan, Elad STOC '21: "Boosting Simple Learners ..." Article: stoc21main-p105-p (type: Full Paper) doi:10.1145/3406325.3451030
Hązła, Jan STOC '21: "On Codes Decoding a Constant ..." Article: stoc21main-p63-p (type: Full Paper) doi:10.1145/3406325.3451015
He, Kun STOC '21: "Sampling Constraint Satisfaction ..." Article: stoc21main-p369-p (type: Full Paper) doi:10.1145/3406325.3451101
Hershkowitz, D. Ellis STOC '21: "Tree Embeddings for Hop-Constrained ..." Article: stoc21main-p175-p (type: Full Paper) doi:10.1145/3406325.3451053
Hirahara, Shuichi STOC '21: "Average-Case Hardness of NP ..." Article: stoc21main-p215-p (type: Full Paper) doi:10.1145/3406325.3451065
Hollender, Alexandros STOC '21: "The Complexity of Gradient ..." Article: stoc21main-p173-p (type: Full Paper) doi:10.1145/3406325.3451052
Holmgren, Justin STOC '21: "Fiat–Shamir via List-Recoverable ..." Article: stoc21main-p422-p (type: Full Paper) doi:10.1145/3406325.3451116
Hongler, Clément STOC '21: "Neural Tangent Kernel: Convergence ..." Article: stoc21invited-inv7-p (type: Abstract (1 page)) doi:10.1145/3406325.3465355
Hrubes, Pavel STOC '21: "Learnability Can Be Independent ..." Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360
Huang, Zhiyi STOC '21: "Online Stochastic Matching, ..." Article: stoc21main-p277-p (type: Full Paper) doi:10.1145/3406325.3451079
Husić, Edin STOC '21: "Approximating Nash Social ..." Article: stoc21main-p113-p (type: Full Paper) doi:10.1145/3406325.3451031
Jacot, Arthur STOC '21: "Neural Tangent Kernel: Convergence ..." Article: stoc21invited-inv7-p (type: Abstract (1 page)) doi:10.1145/3406325.3465355
Jain, Aayush STOC '21: "Indistinguishability Obfuscation ..." Article: stoc21main-p329-p (type: Full Paper) doi:10.1145/3406325.3451093
Jain, Vishesh STOC '21: "Perfectly Sampling k ..." Article: stoc21main-p56-p (type: Full Paper) doi:10.1145/3406325.3451012
Janczewski, Wojciech STOC '21: "Fully Dynamic Approximation ..." Article: stoc21main-p455-p (type: Full Paper) doi:10.1145/3406325.3451137
Jansen, Bart M. P. STOC '21: "Vertex Deletion Parameterized ..." Article: stoc21main-p239-p (type: Full Paper) doi:10.1145/3406325.3451068
Jawale, Ruta STOC '21: "SNARGs for Bounded Depth Computations ..." Article: stoc21main-p180-p (type: Full Paper) doi:10.1145/3406325.3451055
Jayaram, Rajesh STOC '21: "A Polynomial-Time Approximation ..." Article: stoc21invited-inv5-p (type: Abstract (1 page)) doi:10.1145/3406325.3465353 STOC '21: "When Is Approximate Counting ..." Article: stoc21main-p60-p (type: Full Paper) doi:10.1145/3406325.3451014
Jeronimo, Fernando Granha STOC '21: "Near-Linear Time Decoding ..." Article: stoc21main-p474-p (type: Full Paper) doi:10.1145/3406325.3451126
Jia, He STOC '21: "Reducing Isotropy and Volume ..." Article: stoc21main-p73-p (type: Full Paper) doi:10.1145/3406325.3451018
Jiang, Shunhua STOC '21: "A Faster Algorithm for Solving ..." Article: stoc21main-p191-p (type: Full Paper) doi:10.1145/3406325.3451058
Jung, Christopher STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Kalai, Yael Tauman STOC '21: "SNARGs for Bounded Depth Computations ..." Article: stoc21main-p180-p (type: Full Paper) doi:10.1145/3406325.3451055
Kandiros, Anthimos Vardis STOC '21: "Learning Ising Models from ..." Article: stoc21main-p266-p (type: Full Paper) doi:10.1145/3406325.3451074
Kane, Daniel M. STOC '21: "Efficiently Learning Halfspaces ..." Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998 STOC '21: "Optimal Testing of Discrete ..." Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997
Kapralov, Michael STOC '21: "Towards Tight Bounds for Spectral ..." Article: stoc21main-p205-p (type: Full Paper) doi:10.1145/3406325.3451061
Karlin, Anna R. STOC '21: "A (Slightly) Improved Approximation ..." Article: stoc21main-p49-p (type: Full Paper) doi:10.1145/3406325.3451009
Kaufman, Tali STOC '21: "New Cosystolic Expanders from ..." Article: stoc21main-p99-p (type: Full Paper) doi:10.1145/3406325.3451029
Keller, Nathan STOC '21: "Local Concentration Inequalities ..." Article: stoc21main-p55-p (type: Full Paper) doi:10.1145/3406325.3451011
Kelley, Zander STOC '21: "An Improved Derandomization ..." Article: stoc21main-p176-p (type: Full Paper) doi:10.1145/3406325.3451054
Khot, Subhash STOC '21: "Optimal Inapproximability ..." Article: stoc21main-p29-p (type: Full Paper) doi:10.1145/3406325.3451003
Khurana, Dakshita STOC '21: "SNARGs for Bounded Depth Computations ..." Article: stoc21main-p180-p (type: Full Paper) doi:10.1145/3406325.3451055
Kim, Isaac H. STOC '21: "The Ghost in the Radiation: ..." Article: stoc21invited-inv9-p (type: Abstract (1 page)) doi:10.1145/3406325.3465357
Kim, Michael P. STOC '21: "Outcome Indistinguishability ..." Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064
Kingsford, Carl STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
Klein, Nathan STOC '21: "A (Slightly) Improved Approximation ..." Article: stoc21main-p49-p (type: Full Paper) doi:10.1145/3406325.3451009
Klein, Ohad STOC '21: "Local Concentration Inequalities ..." Article: stoc21main-p55-p (type: Full Paper) doi:10.1145/3406325.3451011
Klein, Philip N. STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." Article: stoc21main-p379-p (type: Full Paper) doi:10.1145/3406325.3451103
Kleinberg, Jon STOC '21: "Simplicity Creates Inequity: ..." Article: stoc21invited-inv8-p (type: Abstract (1 page)) doi:10.1145/3406325.3465356
Knop, Alexander STOC '21: "Statistical Query Complexity ..." Article: stoc21main-p11-p (type: Full Paper) doi:10.1145/3406325.3451135 STOC '21: "Log-Rank and Lifting for AND-Functions ..." Article: stoc21main-p21-p (type: Full Paper) doi:10.1145/3406325.3450999
Knudsen, Jakob Bæk Tejs STOC '21: "Load Balancing with Dynamic ..." Article: stoc21main-p394-p (type: Full Paper) doi:10.1145/3406325.3451107
Kociumaka, Tomasz STOC '21: "Improved Dynamic Algorithms ..." Article: stoc21main-p95-p (type: Full Paper) doi:10.1145/3406325.3451026
Kol, Gillat STOC '21: "Optimal Error Resilience of ..." Article: stoc21main-p273-p (type: Full Paper) doi:10.1145/3406325.3451077 STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038
Kontonis, Vasilis STOC '21: "Efficiently Learning Halfspaces ..." Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998
Kothari, Pravesh K. STOC '21: "Playing Unique Games on Certified ..." Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099
Kothari, Robin STOC '21: "Degree vs. Approximate Degree ..." Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047
Krauthgamer, Robert STOC '21: "Subcubic Algorithms for Gomory–Hu ..." Article: stoc21main-p262-p (type: Full Paper) doi:10.1145/3406325.3451073 STOC '21: "Towards Tight Bounds for Spectral ..." Article: stoc21main-p205-p (type: Full Paper) doi:10.1145/3406325.3451061
Krishnamurthy, Akshay STOC '21: "Contextual Search in the Presence ..." Article: stoc21main-p449-p (type: Full Paper) doi:10.1145/3406325.3451120
Kuhn, Fabian STOC '21: "Efficient Randomized Distributed ..." Article: stoc21main-p317-p (type: Full Paper) doi:10.1145/3406325.3451089
Kumar, Mrinal STOC '21: "Decoding Multivariate Multiplicity ..." Article: stoc21main-p97-p (type: Full Paper) doi:10.1145/3406325.3451027
Kumar, Ravi STOC '21: "Sample-Efficient Proper PAC ..." Article: stoc21main-p98-p (type: Full Paper) doi:10.1145/3406325.3451028
Kuszmaul, William STOC '21: "How Asymmetry Helps Buffer ..." Article: stoc21main-p117-p (type: Full Paper) doi:10.1145/3406325.3451033
Laddha, Aditi STOC '21: "Reducing Isotropy and Volume ..." Article: stoc21main-p73-p (type: Full Paper) doi:10.1145/3406325.3451018
Langley, Zachary STOC '21: "A Framework for Dynamic Matching ..." Article: stoc21main-p418-p (type: Full Paper) doi:10.1145/3406325.3451113
Lazos, Philip STOC '21: "Efficient Two-Sided Markets ..." Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076
Le, Hung STOC '21: "Clan Embeddings into Trees, ..." Article: stoc21main-p148-p (type: Full Paper) doi:10.1145/3406325.3451043
Leake, Jonathan STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..." Article: stoc21main-p332-p (type: Full Paper) doi:10.1145/3406325.3451094 STOC '21: "Capacity Lower Bounds via ..." Article: stoc21main-p381-p (type: Full Paper) doi:10.1145/3406325.3451105
Lee, Euiwoong STOC '21: "A Framework for Quadratic ..." Article: stoc21main-p483-p (type: Full Paper) doi:10.1145/3406325.3451128
Lee, Yin Tat STOC '21: "Reducing Isotropy and Volume ..." Article: stoc21main-p73-p (type: Full Paper) doi:10.1145/3406325.3451018 STOC '21: "A Nearly-Linear Time Algorithm ..." Article: stoc21main-p185-p (type: Full Paper) doi:10.1145/3406325.3451056 STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Leme, Renato Paes STOC '21: "Combinatorial Bernoulli Factories: ..." Article: stoc21main-p250-p (type: Full Paper) doi:10.1145/3406325.3451072
Leonardi, Stefano STOC '21: "Flow Time Scheduling with ..." Article: stoc21main-p83-p (type: Full Paper) doi:10.1145/3406325.3451023 STOC '21: "Efficient Two-Sided Markets ..." Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076
Levin, Leonid A. STOC '21: "Climbing Algorithms (Invited ..." Article: stoc21invited-inv1-p (type: Extended Abstract (4 pages)) doi:10.1145/3406325.3457137
Li, Jason STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." Article: stoc21main-p379-p (type: Full Paper) doi:10.1145/3406325.3451103 STOC '21: "Approximate Gomory–Hu Tree ..." Article: stoc21main-p417-p (type: Full Paper) doi:10.1145/3406325.3451112 STOC '21: "Vertex Connectivity in Poly-logarithmic ..." Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088 STOC '21: "Deterministic Mincut in Almost-Linear ..." Article: stoc21main-p420-p (type: Full Paper) doi:10.1145/3406325.3451114
Li, Ray STOC '21: "Settling SETH vs. Approximate ..." Article: stoc21main-p155-p (type: Full Paper) doi:10.1145/3406325.3451045
Li, Yingkai STOC '21: "Revelation Gap for Pricing ..." Article: stoc21main-p189-p (type: Full Paper) doi:10.1145/3406325.3451057
Ligett, Katrina STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Lin, Bingkai STOC '21: "Constant Approximating k-Clique ..." Article: stoc21main-p65-p (type: Full Paper) doi:10.1145/3406325.3451016
Lin, Huijia STOC '21: "Indistinguishability Obfuscation ..." Article: stoc21main-p329-p (type: Full Paper) doi:10.1145/3406325.3451093
Liu, Allen STOC '21: "Settling the Robust Learnability ..." Article: stoc21main-p304-p (type: Full Paper) doi:10.1145/3406325.3451084
Liu, Kuikui STOC '21: "Optimal Mixing of Glauber ..." Article: stoc21main-p121-p (type: Full Paper) doi:10.1145/3406325.3451035 STOC '21: "Log-Concave Polynomials IV: ..." Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091
Liu, Yang P. STOC '21: "Discrepancy Minimization via ..." Article: stoc21main-p2-p (type: Full Paper) doi:10.1145/3406325.3450994 STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Liu, Yanyi STOC '21: "Cryptography from Sublinear-Time ..." Article: stoc21main-p452-p (type: Full Paper) doi:10.1145/3406325.3451121
Lokshtanov, Daniel STOC '21: "Finding Large Induced Sparse ..." Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034
Lombardi, Alex STOC '21: "Fiat–Shamir via List-Recoverable ..." Article: stoc21main-p422-p (type: Full Paper) doi:10.1145/3406325.3451116
Lovett, Shachar STOC '21: "Log-Rank and Lifting for AND-Functions ..." Article: stoc21main-p21-p (type: Full Paper) doi:10.1145/3406325.3450999
Lu, Zhenjian STOC '21: "Pseudodeterministic Algorithms ..." Article: stoc21main-p306-p (type: Full Paper) doi:10.1145/3406325.3451085
Lykouris, Thodoris STOC '21: "Contextual Search in the Presence ..." Article: stoc21main-p449-p (type: Full Paper) doi:10.1145/3406325.3451120
Lyu, Xin STOC '21: "Inverse-Exponential Correlation ..." Article: stoc21main-p491-p (type: Full Paper) doi:10.1145/3406325.3451132
Mangoubi, Oren STOC '21: "Greedy Adversarial Equilibrium: ..." Article: stoc21main-p340-p (type: Full Paper) doi:10.1145/3406325.3451097
Manurangsi, Pasin STOC '21: "Sample-Efficient Proper PAC ..." Article: stoc21main-p98-p (type: Full Paper) doi:10.1145/3406325.3451028
Maus, Yannic STOC '21: "Efficient Randomized Distributed ..." Article: stoc21main-p317-p (type: Full Paper) doi:10.1145/3406325.3451089
McGuire, Sam STOC '21: "Log-Rank and Lifting for AND-Functions ..." Article: stoc21main-p21-p (type: Full Paper) doi:10.1145/3406325.3450999
McKenzie, Theo STOC '21: "Support of Closed Walks and ..." Article: stoc21main-p488-p (type: Full Paper) doi:10.1145/3406325.3451129
McSwiggen, Colin STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..." Article: stoc21main-p332-p (type: Full Paper) doi:10.1145/3406325.3451094
Minzer, Dor STOC '21: "New Separations Results for ..." Article: stoc21main-p154-p (type: Full Paper) doi:10.1145/3406325.3451044
Moitra, Ankur STOC '21: "Algorithmic Foundations for ..." Article: stoc21main-p276-p (type: Full Paper) doi:10.1145/3406325.3451078 STOC '21: "Settling the Robust Learnability ..." Article: stoc21main-p304-p (type: Full Paper) doi:10.1145/3406325.3451084
Moran, Shay STOC '21: "Learnability Can Be Independent ..." Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360 STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041 STOC '21: "Boosting Simple Learners ..." Article: stoc21main-p105-p (type: Full Paper) doi:10.1145/3406325.3451030 STOC '21: "A Theory of Universal Learning ..." Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087
Moshkovitz, Guy STOC '21: "Structure vs. Randomness for ..." Article: stoc21main-p41-p (type: Full Paper) doi:10.1145/3406325.3451007
Mossel, Elchanan STOC '21: "Robust Testing of Low Dimensional ..." Article: stoc21main-p421-p (type: Full Paper) doi:10.1145/3406325.3451115
Mukhopadhyay, Partha STOC '21: "Lower Bounds for Monotone ..." Article: stoc21main-p241-p (type: Full Paper) doi:10.1145/3406325.3451069
Mukhopadhyay, Sagnik STOC '21: "Distributed Weighted Min-Cut ..." Article: stoc21main-p77-p (type: Full Paper) doi:10.1145/3406325.3451020 STOC '21: "Breaking the Quadratic Barrier ..." Article: stoc21main-p325-p (type: Full Paper) doi:10.1145/3406325.3451092
Mullainathan, Sendhil STOC '21: "Simplicity Creates Inequity: ..." Article: stoc21invited-inv8-p (type: Abstract (1 page)) doi:10.1145/3406325.3465356
N, Vishvajeet STOC '21: "Graph Streaming Lower Bounds ..." Article: stoc21main-p408-p (type: Full Paper) doi:10.1145/3406325.3451110
Nakos, Vasileios STOC '21: "Sparse Nonnegative Convolution ..." Article: stoc21main-p318-p (type: Full Paper) doi:10.1145/3406325.3451090
Nanongkai, Danupon STOC '21: "Distributed Weighted Min-Cut ..." Article: stoc21main-p77-p (type: Full Paper) doi:10.1145/3406325.3451020 STOC '21: "Vertex Connectivity in Poly-logarithmic ..." Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088 STOC '21: "Breaking the Quadratic Barrier ..." Article: stoc21main-p325-p (type: Full Paper) doi:10.1145/3406325.3451092
Naor, Assaf STOC '21: "A Framework for Quadratic ..." Article: stoc21main-p483-p (type: Full Paper) doi:10.1145/3406325.3451128
Naor, Moni STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041
Nederlof, Jesper STOC '21: "Improving Schroeppel and Shamir’s ..." Article: stoc21main-p84-p (type: Full Paper) doi:10.1145/3406325.3451024
Neel, Seth STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Neeman, Joe STOC '21: "Robust Testing of Low Dimensional ..." Article: stoc21main-p421-p (type: Full Paper) doi:10.1145/3406325.3451115
Nekrich, Yakov STOC '21: "Dynamic Planar Point Location ..." Article: stoc21main-p368-p (type: Full Paper) doi:10.1145/3406325.3451100
Niazadeh, Rad STOC '21: "Combinatorial Bernoulli Factories: ..." Article: stoc21main-p250-p (type: Full Paper) doi:10.1145/3406325.3451072
Nisan, Noam STOC '21: "Bipartite Perfect Matching ..." Article: stoc21main-p27-p (type: Full Paper) doi:10.1145/3406325.3451002
Nordström, Jakob STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Nowicki, Krzysztof STOC '21: "A Deterministic Algorithm ..." Article: stoc21main-p80-p (type: Full Paper) doi:10.1145/3406325.3451136
O'Donnell, Ryan STOC '21: "Fiber Bundle Codes: Breaking ..." Article: stoc21main-p32-p (type: Full Paper) doi:10.1145/3406325.3451005 STOC '21: "Improved Quantum Data Analysis ..." Article: stoc21main-p404-p (type: Full Paper) doi:10.1145/3406325.3451109
Oliveira, Igor C. STOC '21: "Pseudodeterministic Algorithms ..." Article: stoc21main-p306-p (type: Full Paper) doi:10.1145/3406325.3451085
Oshman, Rotem STOC '21: "The Communication Complexity ..." Article: stoc21main-p386-p (type: Full Paper) doi:10.1145/3406325.3451106
Pan, Qinxuan STOC '21: "Sample-Optimal and Efficient ..." Article: stoc21main-p39-p (type: Full Paper) doi:10.1145/3406325.3451006
Panigrahi, Debmalya STOC '21: "Approximate Gomory–Hu Tree ..." Article: stoc21main-p417-p (type: Full Paper) doi:10.1145/3406325.3451112 STOC '21: "Vertex Connectivity in Poly-logarithmic ..." Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088
Paramonov, Dmitry STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038
Parisi, Daniel STOC '21: "Entropy Decay in the Swendsen–Wang ..." Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095
Pass, Rafael STOC '21: "Cryptography from Sublinear-Time ..." Article: stoc21main-p452-p (type: Full Paper) doi:10.1145/3406325.3451121 STOC '21: "Indistinguishability Obfuscation ..." Article: stoc21main-p242-p (type: Full Paper) doi:10.1145/3406325.3451070
Peebles, John STOC '21: "Optimal Testing of Discrete ..." Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997
Peleg, Shir STOC '21: "Polynomial Time Deterministic ..." Article: stoc21main-p57-p (type: Full Paper) doi:10.1145/3406325.3451013
Peri, Noam STOC '21: "Expander Random Walks: A Fourier-Analytic ..." Article: stoc21main-p168-p (type: Full Paper) doi:10.1145/3406325.3451049
Perkins, Will STOC '21: "Frozen 1-RSB Structure of ..." Article: stoc21main-p444-p (type: Full Paper) doi:10.1145/3406325.3451119
Pettie, Seth STOC '21: "Information Theoretic Limits ..." Article: stoc21main-p114-p (type: Full Paper) doi:10.1145/3406325.3451032
Pich, Ján STOC '21: "Strong Co-nondeterministic ..." Article: stoc21main-p436-p (type: Full Paper) doi:10.1145/3406325.3451117
Pilipczuk, Marcin STOC '21: "Finding Large Induced Sparse ..." Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034
Pilipczuk, Michał STOC '21: "Finding Large Induced Sparse ..." Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034
Pitassi, Toniann STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Podimata, Chara STOC '21: "Contextual Search in the Presence ..." Article: stoc21main-p449-p (type: Full Paper) doi:10.1145/3406325.3451120
Prasad, Adarsh STOC '21: "Robust Linear Regression: ..." Article: stoc21main-p26-p (type: Full Paper) doi:10.1145/3406325.3451001
Preskill, John STOC '21: "The Ghost in the Radiation: ..." Article: stoc21invited-inv9-p (type: Abstract (1 page)) doi:10.1145/3406325.3465357
Price, Eric STOC '21: "Near-Optimal Learning of Tree-Structured ..." Article: stoc21main-p217-p (type: Full Paper) doi:10.1145/3406325.3451066 STOC '21: "Optimal Testing of Discrete ..." Article: stoc21main-p12-p (type: Full Paper) doi:10.1145/3406325.3450997
Qiao, Mingda STOC '21: "Stronger Calibration Lower ..." Article: stoc21main-p170-p (type: Full Paper) doi:10.1145/3406325.3451050
Rao, Shravas STOC '21: "Degree vs. Approximate Degree ..." Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047
Rasmussen, Peter Michael Reichstein STOC '21: "Support of Closed Walks and ..." Article: stoc21main-p488-p (type: Full Paper) doi:10.1145/3406325.3451129
Regev, Oded STOC '21: "Continuous LWE ..." Article: stoc21main-p24-p (type: Full Paper) doi:10.1145/3406325.3451000
Reiffenhäuser, Rebecca STOC '21: "Efficient Two-Sided Markets ..." Article: stoc21main-p271-p (type: Full Paper) doi:10.1145/3406325.3451076
Reingold, Omer STOC '21: "Outcome Indistinguishability ..." Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064
Remscrim, Zachary STOC '21: "Eliminating Intermediate Measurements ..." Article: stoc21main-p171-p (type: Full Paper) doi:10.1145/3406325.3451051
Riveros, Cristian STOC '21: "A Polynomial-Time Approximation ..." Article: stoc21invited-inv5-p (type: Abstract (1 page)) doi:10.1145/3406325.3465353 STOC '21: "When Is Approximate Counting ..." Article: stoc21main-p60-p (type: Full Paper) doi:10.1145/3406325.3451014
Robere, Robert STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Rohwedder, Lars STOC '21: "A (2 + ε)-Approximation ..." Article: stoc21main-p269-p (type: Full Paper) doi:10.1145/3406325.3451075
Ron, Shiri STOC '21: "The Communication Complexity ..." Article: stoc21main-p303-p (type: Full Paper) doi:10.1145/3406325.3451083
Ron-Zewi, Noga STOC '21: "Efficient List-Decoding with ..." Article: stoc21main-p156-p (type: Full Paper) doi:10.1145/3406325.3451046
Roth, Aaron STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Roth, Tal STOC '21: "The Communication Complexity ..." Article: stoc21main-p386-p (type: Full Paper) doi:10.1145/3406325.3451106
Rothblum, Guy N. STOC '21: "Outcome Indistinguishability ..." Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064
Rothblum, Ron D. STOC '21: "Fiat–Shamir via List-Recoverable ..." Article: stoc21main-p422-p (type: Full Paper) doi:10.1145/3406325.3451116
Ruan, Yufei STOC '21: "Linear Bandits with Limited ..." Article: stoc21main-p31-p (type: Full Paper) doi:10.1145/3406325.3451004
Rubin, Natan STOC '21: "Stronger Bounds for Weak Epsilon-Nets ..." Article: stoc21main-p209-p (type: Full Paper) doi:10.1145/3406325.3451062
Rubinstein, Aviad STOC '21: "The Randomized Communication ..." Article: stoc21main-p414-p (type: Full Paper) doi:10.1145/3406325.3451111 STOC '21: "Exponential Communication ..." Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127 STOC '21: "Settling the Complexity of ..." Article: stoc21main-p132-p (type: Full Paper) doi:10.1145/3406325.3451039
Rzążewski, Paweł STOC '21: "Finding Large Induced Sparse ..." Article: stoc21main-p119-p (type: Full Paper) doi:10.1145/3406325.3451034
Sah, Ashwin STOC '21: "Perfectly Sampling k ..." Article: stoc21main-p56-p (type: Full Paper) doi:10.1145/3406325.3451012
Sahai, Amit STOC '21: "Indistinguishability Obfuscation ..." Article: stoc21main-p329-p (type: Full Paper) doi:10.1145/3406325.3451093
Saket, Rishi STOC '21: "Hardness of Learning DNFs ..." Article: stoc21main-p228-p (type: Full Paper) doi:10.1145/3406325.3451067
Samorodnitsky, Alex STOC '21: "On Codes Decoding a Constant ..." Article: stoc21main-p63-p (type: Full Paper) doi:10.1145/3406325.3451015
Sandholm, Tuomas STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
Santhanam, Rahul STOC '21: "Strong Co-nondeterministic ..." Article: stoc21main-p436-p (type: Full Paper) doi:10.1145/3406325.3451117 STOC '21: "Iterated Lower Bound Formulas: ..." Article: stoc21main-p50-p (type: Full Paper) doi:10.1145/3406325.3451010 STOC '21: "Pseudodeterministic Algorithms ..." Article: stoc21main-p306-p (type: Full Paper) doi:10.1145/3406325.3451085
Saraf, Shubhangi STOC '21: "Reconstruction Algorithms ..." Article: stoc21main-p336-p (type: Full Paper) doi:10.1145/3406325.3451096
Saranurak, Thatchaphol STOC '21: "Vertex Connectivity in Poly-logarithmic ..." Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088 STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Saulpic, David STOC '21: "A New Coreset Framework for ..." Article: stoc21main-p81-p (type: Full Paper) doi:10.1145/3406325.3451022
Savani, Rahul STOC '21: "The Complexity of Gradient ..." Article: stoc21main-p173-p (type: Full Paper) doi:10.1145/3406325.3451052
Sawhney, Mehtaab STOC '21: "Perfectly Sampling k ..." Article: stoc21main-p56-p (type: Full Paper) doi:10.1145/3406325.3451012 STOC '21: "Discrepancy Minimization via ..." Article: stoc21main-p2-p (type: Full Paper) doi:10.1145/3406325.3450994
Saxena, Raghuvansh R. STOC '21: "Exponential Communication ..." Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127 STOC '21: "Optimal Error Resilience of ..." Article: stoc21main-p273-p (type: Full Paper) doi:10.1145/3406325.3451077 STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038
Sberlo, Ori STOC '21: "On Codes Decoding a Constant ..." Article: stoc21main-p63-p (type: Full Paper) doi:10.1145/3406325.3451015
Schapire, Robert STOC '21: "Contextual Search in the Presence ..." Article: stoc21main-p449-p (type: Full Paper) doi:10.1145/3406325.3451120
Schneider, Jon STOC '21: "Combinatorial Bernoulli Factories: ..." Article: stoc21main-p250-p (type: Full Paper) doi:10.1145/3406325.3451072
Schramm, Tselil STOC '21: "Playing Unique Games on Certified ..." Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099
Schwartz, Roy STOC '21: "The Metric Relaxation for ..." Article: stoc21main-p246-p (type: Full Paper) doi:10.1145/3406325.3451071
Schwiegelshohn, Chris STOC '21: "A New Coreset Framework for ..." Article: stoc21main-p81-p (type: Full Paper) doi:10.1145/3406325.3451022
Scott, Alex STOC '21: "Optimal Labelling Schemes ..." Article: stoc21main-p374-p (type: Full Paper) doi:10.1145/3406325.3451102
Scully, Ziv STOC '21: "Load Balancing Guardrails: ..." Article: stoc21invited-inv11-p (type: Abstract (1 page)) doi:10.1145/3406325.3465359
Seddighin, Saeed STOC '21: "Improved Dynamic Algorithms ..." Article: stoc21main-p95-p (type: Full Paper) doi:10.1145/3406325.3451026
Shaltiel, Ronen STOC '21: "Explicit Uniquely Decodable ..." Article: stoc21main-p165-p (type: Full Paper) doi:10.1145/3406325.3451048
Sharifi-Malvajerdi, Saeed STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Shenfeld, Moshe STOC '21: "A New Analysis of Differential ..." Article: stoc21invited-inv10-p (type: Abstract (1 page)) doi:10.1145/3406325.3465358
Sherstov, Alexander A. STOC '21: "An Optimal Separation of Randomized ..." Article: stoc21main-p75-p (type: Full Paper) doi:10.1145/3406325.3451019
Shiragur, Kirankumar STOC '21: "Fractionally Log-Concave and ..." Article: stoc21main-p456-p (type: Full Paper) doi:10.1145/3406325.3451123
Shpilka, Amir STOC '21: "Learnability Can Be Independent ..." Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360 STOC '21: "Polynomial Time Deterministic ..." Article: stoc21main-p57-p (type: Full Paper) doi:10.1145/3406325.3451013
Shu, Xinkai STOC '21: "Online Stochastic Matching, ..." Article: stoc21main-p277-p (type: Full Paper) doi:10.1145/3406325.3451079
Sidford, Aaron STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Silbak, Jad STOC '21: "Explicit Uniquely Decodable ..." Article: stoc21main-p165-p (type: Full Paper) doi:10.1145/3406325.3451048
Sinclair, Alistair STOC '21: "Entropy Decay in the Swendsen–Wang ..." Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095
Sinha, Makrand STOC '21: "k-Forrelation Optimally Separates ..." Article: stoc21main-p141-p (type: Full Paper) doi:10.1145/3406325.3451040
Skoulakis, Stratis STOC '21: "The Complexity of Constrained ..." Article: stoc21main-p470-p (type: Full Paper) doi:10.1145/3406325.3451125
Smith, Adam STOC '21: "When Is Memorization of Irrelevant ..." Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131
Sokolov, Dmitry STOC '21: "Automating Algebraic Proof ..." Article: stoc21main-p280-p (type: Full Paper) doi:10.1145/3406325.3451080
Song, Min Jae STOC '21: "Continuous LWE ..." Article: stoc21main-p24-p (type: Full Paper) doi:10.1145/3406325.3451000
Song, Zhao STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038 STOC '21: "A Faster Algorithm for Solving ..." Article: stoc21main-p191-p (type: Full Paper) doi:10.1145/3406325.3451058 STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Srivastava, Nikhil STOC '21: "Support of Closed Walks and ..." Article: stoc21main-p488-p (type: Full Paper) doi:10.1145/3406325.3451129
Srivastava, Shashank STOC '21: "Near-Linear Time Decoding ..." Article: stoc21main-p474-p (type: Full Paper) doi:10.1145/3406325.3451126
Steurer, David STOC '21: "Playing Unique Games on Certified ..." Article: stoc21main-p363-p (type: Full Paper) doi:10.1145/3406325.3451099
Storozhenko, Andrey A. STOC '21: "An Optimal Separation of Randomized ..." Article: stoc21main-p75-p (type: Full Paper) doi:10.1145/3406325.3451019
Sudan, Madhu STOC '21: "Decoding Multivariate Multiplicity ..." Article: stoc21main-p97-p (type: Full Paper) doi:10.1145/3406325.3451027
Sun, Nike STOC '21: "Statistical Physics of Random ..." Article: stoc21invited-inv4-p (type: Abstract (1 page)) doi:10.1145/3406325.3465352
Tal, Avishay STOC '21: "Degree vs. Approximate Degree ..." Article: stoc21main-p159-p (type: Full Paper) doi:10.1145/3406325.3451047
Talwar, Kunal STOC '21: "When Is Memorization of Irrelevant ..." Article: stoc21main-p490-p (type: Full Paper) doi:10.1145/3406325.3451131
Tang, Eugene STOC '21: "The Ghost in the Radiation: ..." Article: stoc21invited-inv9-p (type: Abstract (1 page)) doi:10.1145/3406325.3465357
Tang, Yi STOC '21: "Continuous LWE ..." Article: stoc21main-p24-p (type: Full Paper) doi:10.1145/3406325.3451000
Tang, Ziye STOC '21: "Chasing Convex Bodies with ..." Article: stoc21invited-inv6-p (type: Abstract (1 page)) doi:10.1145/3406325.3465354
Tardos, Jakab STOC '21: "Towards Tight Bounds for Spectral ..." Article: stoc21main-p205-p (type: Full Paper) doi:10.1145/3406325.3451061
Ta-Shma, Amnon STOC '21: "Expander Random Walks: A Fourier-Analytic ..." Article: stoc21main-p168-p (type: Full Paper) doi:10.1145/3406325.3451049
Tell, Roei STOC '21: "Simple and Fast Derandomization ..." Article: stoc21main-p192-p (type: Full Paper) doi:10.1145/3406325.3451059
Tessler, Ran J. STOC '21: "New Cosystolic Expanders from ..." Article: stoc21main-p99-p (type: Full Paper) doi:10.1145/3406325.3451029
Thomas, Clayton STOC '21: "Exponential Communication ..." Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127
Thorup, Mikkel STOC '21: "Load Balancing with Dynamic ..." Article: stoc21main-p394-p (type: Full Paper) doi:10.1145/3406325.3451107
Tonoyan, Tigran STOC '21: "Efficient Randomized Distributed ..." Article: stoc21main-p317-p (type: Full Paper) doi:10.1145/3406325.3451089
Touitou, Noam STOC '21: "Flow Time Scheduling with ..." Article: stoc21main-p83-p (type: Full Paper) doi:10.1145/3406325.3451023
Trabelsi, Ohad STOC '21: "Subcubic Algorithms for Gomory–Hu ..." Article: stoc21main-p262-p (type: Full Paper) doi:10.1145/3406325.3451073
Traub, Vera STOC '21: "Bridging the Gap between Tree ..." Article: stoc21main-p308-p (type: Full Paper) doi:10.1145/3406325.3451086
Tulsiani, Madhur STOC '21: "Near-Linear Time Decoding ..." Article: stoc21main-p474-p (type: Full Paper) doi:10.1145/3406325.3451126
Tur, Nitzan STOC '21: "The Metric Relaxation for ..." Article: stoc21main-p246-p (type: Full Paper) doi:10.1145/3406325.3451071
Tzameret, Iddo STOC '21: "Iterated Lower Bound Formulas: ..." Article: stoc21main-p50-p (type: Full Paper) doi:10.1145/3406325.3451010
Tzamos, Christos STOC '21: "Efficiently Learning Halfspaces ..." Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998
Ullman, Jonathan STOC '21: "The Limits of Pan Privacy ..." Article: stoc21main-p3-p (type: Full Paper) doi:10.1145/3406325.3450995
Valiant, Gregory STOC '21: "Stronger Calibration Lower ..." Article: stoc21main-p170-p (type: Full Paper) doi:10.1145/3406325.3451050
Van den Brand, Jan STOC '21: "Breaking the Quadratic Barrier ..." Article: stoc21main-p325-p (type: Full Paper) doi:10.1145/3406325.3451092 STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Van Handel, Ramon STOC '21: "A Theory of Universal Learning ..." Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087
Vazirani, Umesh STOC '21: "(Sub)Exponential Advantage ..." Article: stoc21main-p194+p370-p (type: Full Paper) doi:10.1145/3406325.3451060
Végh, László A. STOC '21: "Approximating Nash Social ..." Article: stoc21main-p113-p (type: Full Paper) doi:10.1145/3406325.3451031
Vempala, Santosh STOC '21: "Reducing Isotropy and Volume ..." Article: stoc21main-p73-p (type: Full Paper) doi:10.1145/3406325.3451018
Vigoda, Eric STOC '21: "Optimal Mixing of Glauber ..." Article: stoc21main-p121-p (type: Full Paper) doi:10.1145/3406325.3451035 STOC '21: "Entropy Decay in the Swendsen–Wang ..." Article: stoc21main-p333-p (type: Full Paper) doi:10.1145/3406325.3451095
Vinodchandran, N. V. STOC '21: "Near-Optimal Learning of Tree-Structured ..." Article: stoc21main-p217-p (type: Full Paper) doi:10.1145/3406325.3451066
Vinzant, Cynthia STOC '21: "Log-Concave Polynomials in ..." Article: stoc21invited-inv3-p (type: Abstract (1 page)) doi:10.1145/3406325.3465351 STOC '21: "Log-Concave Polynomials IV: ..." Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091
Vishnoi, Nisheeth K. STOC '21: "Greedy Adversarial Equilibrium: ..." Article: stoc21main-p340-p (type: Full Paper) doi:10.1145/3406325.3451097 STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..." Article: stoc21main-p332-p (type: Full Paper) doi:10.1145/3406325.3451094
Vitercik, Ellen STOC '21: "How Much Data Is Sufficient ..." Article: stoc21main-p122-p (type: Full Paper) doi:10.1145/3406325.3451036
Volkovich, Ilya STOC '21: "Reconstruction Algorithms ..." Article: stoc21main-p336-p (type: Full Paper) doi:10.1145/3406325.3451096
Vuong, Thuy-Duong STOC '21: "Log-Concave Polynomials IV: ..." Article: stoc21main-p322-p (type: Full Paper) doi:10.1145/3406325.3451091 STOC '21: "Fractionally Log-Concave and ..." Article: stoc21main-p456-p (type: Full Paper) doi:10.1145/3406325.3451123
Wajc, David STOC '21: "Universally-Optimal Distributed ..." Article: stoc21main-p285-p (type: Full Paper) doi:10.1145/3406325.3451081
Wang, Di STOC '21: "Minimum Cost Flows, MDPs, ..." Article: stoc21main-p396-p (type: Full Paper) doi:10.1145/3406325.3451108
Wang, Dingyu STOC '21: "Information Theoretic Limits ..." Article: stoc21main-p114-p (type: Full Paper) doi:10.1145/3406325.3451032
Wang, Haitao STOC '21: "A New Algorithm for Euclidean ..." Article: stoc21main-p128-p (type: Full Paper) doi:10.1145/3406325.3451037
Węgrzycki, Karol STOC '21: "Improving Schroeppel and Shamir’s ..." Article: stoc21main-p84-p (type: Full Paper) doi:10.1145/3406325.3451024
Wein, Nicole STOC '21: "Tight Conditional Lower Bounds ..." Article: stoc21main-p489-p (type: Full Paper) doi:10.1145/3406325.3451130
Weinberg, S. Matthew STOC '21: "Exponential Communication ..." Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127
Weinstein, Omri STOC '21: "A Faster Algorithm for Solving ..." Article: stoc21main-p191-p (type: Full Paper) doi:10.1145/3406325.3451058
Wiese, Andreas STOC '21: "A (2 + ε)-Approximation ..." Article: stoc21main-p269-p (type: Full Paper) doi:10.1145/3406325.3451075
Włodarczyk, Michał STOC '21: "Vertex Deletion Parameterized ..." Article: stoc21main-p239-p (type: Full Paper) doi:10.1145/3406325.3451068
Woelfel, Philipp STOC '21: "Efficient Randomized DCAS ..." Article: stoc21main-p497-p (type: Full Paper) doi:10.1145/3406325.3451133
Wu, Pei STOC '21: "An Optimal Separation of Randomized ..." Article: stoc21main-p75-p (type: Full Paper) doi:10.1145/3406325.3451019
Xu, Changji STOC '21: "Frozen 1-RSB Structure of ..." Article: stoc21main-p444-p (type: Full Paper) doi:10.1145/3406325.3451119
Yang, Jiaqi STOC '21: "Linear Bandits with Limited ..." Article: stoc21main-p31-p (type: Full Paper) doi:10.1145/3406325.3451004
Ye, Guanghao STOC '21: "A Nearly-Linear Time Algorithm ..." Article: stoc21main-p185-p (type: Full Paper) doi:10.1145/3406325.3451056
Yehudayoff, Amir STOC '21: "Learnability Can Be Independent ..." Article: stoc21invited-inv12-p (type: Abstract (1 page)) doi:10.1145/3406325.3465360 STOC '21: "A Theory of Universal Learning ..." Article: stoc21main-p310-p (type: Full Paper) doi:10.1145/3406325.3451087
Yin, Yitong STOC '21: "Sampling Constraint Satisfaction ..." Article: stoc21main-p369-p (type: Full Paper) doi:10.1145/3406325.3451101
Yingchareonthawornchai, Sorrachai STOC '21: "Vertex Connectivity in Poly-logarithmic ..." Article: stoc21main-p314-p (type: Full Paper) doi:10.1145/3406325.3451088
Yogev, Eylon STOC '21: "Adversarial Laws of Large ..." Article: stoc21main-p145-p (type: Full Paper) doi:10.1145/3406325.3451041
Yona, Gal STOC '21: "Outcome Indistinguishability ..." Article: stoc21main-p211-p (type: Full Paper) doi:10.1145/3406325.3451064
Yoshida, Yuichi STOC '21: "Towards Tight Bounds for Spectral ..." Article: stoc21main-p205-p (type: Full Paper) doi:10.1145/3406325.3451061
Yu, Huacheng STOC '21: "Almost Optimal Super-Constant-Pass ..." Article: stoc21main-p129-p (type: Full Paper) doi:10.1145/3406325.3451038
Yuan, Weiqiang STOC '21: "Log-Rank and Lifting for AND-Functions ..." Article: stoc21main-p21-p (type: Full Paper) doi:10.1145/3406325.3450999
Zampetakis, Manolis STOC '21: "The Complexity of Constrained ..." Article: stoc21main-p470-p (type: Full Paper) doi:10.1145/3406325.3451125
Zarifis, Nikos STOC '21: "Efficiently Learning Halfspaces ..." Article: stoc21main-p14-p (type: Full Paper) doi:10.1145/3406325.3450998
Zenklusen, Rico STOC '21: "Bridging the Gap between Tree ..." Article: stoc21main-p308-p (type: Full Paper) doi:10.1145/3406325.3451086
Zhang, Hengjie STOC '21: "A Faster Algorithm for Solving ..." Article: stoc21main-p191-p (type: Full Paper) doi:10.1145/3406325.3451058
Zhang, Jiayu STOC '21: "Succinct Blind Quantum Computation ..." Article: stoc21main-p302-p (type: Full Paper) doi:10.1145/3406325.3451082
Zhang, Rachel STOC '21: "SNARGs for Bounded Depth Computations ..." Article: stoc21main-p180-p (type: Full Paper) doi:10.1145/3406325.3451055
Zhao, Junyao STOC '21: "The Randomized Communication ..." Article: stoc21main-p414-p (type: Full Paper) doi:10.1145/3406325.3451111 STOC '21: "Exponential Communication ..." Article: stoc21main-p480-p (type: Full Paper) doi:10.1145/3406325.3451127
Zhou, Yuan STOC '21: "Linear Bandits with Limited ..." Article: stoc21main-p31-p (type: Full Paper) doi:10.1145/3406325.3451004
Zuzic, Goran STOC '21: "Universally-Optimal Distributed ..." Article: stoc21main-p285-p (type: Full Paper) doi:10.1145/3406325.3451081 STOC '21: "Hop-Constrained Oblivious ..." Article: stoc21main-p344-p (type: Full Paper) doi:10.1145/3406325.3451098 STOC '21: "Tree Embeddings for Hop-Constrained ..." Article: stoc21main-p175-p (type: Full Paper) doi:10.1145/3406325.3451053

438 authors

proc time: 0.61