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 ..."
Aamari, Eddie STOC '21: "Statistical Query Complexity ..."
Aaronson, Scott STOC '21: "Degree vs. Approximate Degree ..."
Abboud, Amir STOC '21: "Subcubic Algorithms for Gomory–Hu ..."
Aho, Alfred V. STOC '21: "Computational Thinking in ..."
Alimohammadi, Yeganeh STOC '21: "Fractionally Log-Concave and ..."
Alman, Josh STOC '21: "Kronecker Products, Low-Depth ..."
Alon, Noga STOC '21: "Boosting Simple Learners ..." STOC '21: "Adversarial Laws of Large ..."
Alweiss, Ryan STOC '21: "Discrepancy Minimization via ..."
Anari, Nima STOC '21: "Log-Concave Polynomials in ..." STOC '21: "Fractionally Log-Concave and ..." STOC '21: "Log-Concave Polynomials IV: ..."
Arenas, Marcelo STOC '21: "A Polynomial-Time Approximation ..." STOC '21: "When Is Approximate Counting ..."
Argue, C. J. STOC '21: "Chasing Convex Bodies with ..."
Assadi, Sepehr STOC '21: "Graph Streaming Lower Bounds ..."
Azar, Yossi STOC '21: "Flow Time Scheduling with ..."
Babichenko, Yakov STOC '21: "Settling the Complexity of ..."
Bădescu, Costin STOC '21: "Improved Quantum Data Analysis ..."
Bafna, Mitali STOC '21: "Playing Unique Games on Certified ..."
Bakshi, Ainesh STOC '21: "Robust Linear Regression: ..."
Balcan, Maria-Florina STOC '21: "How Much Data Is Sufficient ..."
Bansal, Nikhil STOC '21: "k-Forrelation Optimally Separates ..."
Barak, Boaz STOC '21: "Playing Unique Games on Certified ..."
Bartal, Yair STOC '21: "Near-Linear Time Approximation ..."
Ben-David, Shai STOC '21: "Learnability Can Be Independent ..."
Ben-David, Shalev STOC '21: "Degree vs. Approximate Degree ..."
Ben-Eliezer, Omri STOC '21: "Adversarial Laws of Large ..."
Beniamini, Gal STOC '21: "Bipartite Perfect Matching ..."
Bernstein, Aaron STOC '21: "A Framework for Dynamic Matching ..."
Bhandari, Siddharth STOC '21: "Decoding Multivariate Multiplicity ..."
Bhangale, Amey STOC '21: "Optimal Inapproximability ..."
Bhargava, Vishwas STOC '21: "Reconstruction Algorithms ..."
Bhattacharyya, Arnab STOC '21: "Near-Optimal Learning of Tree-Structured ..."
Bhattiprolu, Vijay STOC '21: "A Framework for Quadratic ..."
Blais, Eric STOC '21: "VC Dimension and Distribution-Free ..."
Blanca, Antonio STOC '21: "Entropy Decay in the Swendsen–Wang ..."
Blikstad, Joakim STOC '21: "Breaking the Quadratic Barrier ..."
Bonamy, Marthe STOC '21: "Optimal Labelling Schemes ..."
Bousquet, Olivier STOC '21: "A Theory of Universal Learning ..."
Braverman, Mark STOC '21: "New Separations Results for ..."
Bressan, Marco STOC '21: "Efficient and Near-Optimal ..."
Bringmann, Karl STOC '21: "Sparse Nonnegative Convolution ..."
Brown, Gavin STOC '21: "When Is Memorization of Irrelevant ..."
Bruna, Joan STOC '21: "Continuous LWE ..."
Bun, Mark STOC '21: "When Is Memorization of Irrelevant ..."
Caputo, Pietro STOC '21: "Entropy Decay in the Swendsen–Wang ..."
Cecchetto, Federica STOC '21: "Bridging the Gap between Tree ..."
Chase, Zachary STOC '21: "Separating Words and Trace ..."
Chattopadhyay, Arkadev STOC '21: "Lower Bounds for Monotone ..."
Chen, Lijie STOC '21: "Simple and Fast Derandomization ..." STOC '21: "Inverse-Exponential Correlation ..." STOC '21: "Almost Optimal Super-Constant-Pass ..."
Chen, Sitan STOC '21: "Algorithmic Foundations for ..."
Chen, Zongchen STOC '21: "Optimal Mixing of Glauber ..."
Cheu, Albert STOC '21: "The Limits of Pan Privacy ..."
Chuzhoy, Julia STOC '21: "Decremental All-Pairs Shortest ..."
Cohen, Alex STOC '21: "Structure vs. Randomness for ..."
Cohen, Gil STOC '21: "Expander Random Walks: A Fourier-Analytic ..."
Cohen-Addad, Vincent STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." STOC '21: "A New Coreset Framework for ..."
Croquevielle, Luis Alberto STOC '21: "A Polynomial-Time Approximation ..." STOC '21: "When Is Approximate Counting ..."
Curticapean, Radu STOC '21: "A Full Complexity Dichotomy ..."
Dagan, Yuval STOC '21: "Adversarial Laws of Large ..." STOC '21: "Learning Ising Models from ..."
Dalirrooyfard, Mina STOC '21: "Tight Conditional Lower Bounds ..."
Daskalakis, Constantinos STOC '21: "Sample-Optimal and Efficient ..." STOC '21: "The Complexity of Constrained ..." STOC '21: "Learning Ising Models from ..."
Datta, Rajit STOC '21: "Lower Bounds for Monotone ..."
De, Anindya STOC '21: "Robust Testing of Low Dimensional ..."
DeBlasio, Dan STOC '21: "How Much Data Is Sufficient ..."
De Kroon, Jari J. H. STOC '21: "Vertex Deletion Parameterized ..."
De Rezende, Susanna F. STOC '21: "Automating Algebraic Proof ..."
Dershowitz, Nachum STOC '21: "The Communication Complexity ..."
Diakonikolas, Ilias STOC '21: "Optimal Testing of Discrete ..." STOC '21: "Efficiently Learning Halfspaces ..."
Dick, Travis STOC '21: "How Much Data Is Sufficient ..."
Dikkala, Nishanth STOC '21: "Learning Ising Models from ..."
Dobzinski, Shahar STOC '21: "The Communication Complexity ..."
Dong, Sally STOC '21: "A Nearly-Linear Time Algorithm ..."
Dory, Michal STOC '21: "Distributed Weighted Min-Cut ..."
Dudeja, Aditi STOC '21: "A Framework for Dynamic Matching ..."
Dütting, Paul STOC '21: "Efficient Two-Sided Markets ..."
Dwork, Cynthia STOC '21: "Outcome Indistinguishability ..."
Efremenko, Klim STOC '21: "Optimal Error Resilience of ..."
Efron, Yuval STOC '21: "Distributed Weighted Min-Cut ..."
Esperet, Louis STOC '21: "Optimal Labelling Schemes ..."
Fearnley, John STOC '21: "The Complexity of Gradient ..."
Fefferman, Bill STOC '21: "Eliminating Intermediate Measurements ..."
Feldman, Vitaly STOC '21: "When Is Memorization of Irrelevant ..."
Feng, Weiming STOC '21: "Sampling Constraint Satisfaction ..."
Feng, Yiding STOC '21: "Revelation Gap for Pricing ..."
Ferreira Pinto Jr., Renato STOC '21: "VC Dimension and Distribution-Free ..."
Filtser, Arnold STOC '21: "Clan Embeddings into Trees, ..."
Fischer, Nick STOC '21: "Sparse Nonnegative Convolution ..."
Fusco, Federico STOC '21: "Efficient Two-Sided Markets ..."
Gabriel, Franck STOC '21: "Neural Tangent Kernel: Convergence ..."
Garg, Jugal STOC '21: "Approximating Nash Social ..."
Gartland, Peter STOC '21: "Finding Large Induced Sparse ..."
Gawrychowski, Paweł STOC '21: "Fully Dynamic Approximation ..."
Gay, Romain STOC '21: "Indistinguishability Obfuscation ..."
Gayen, Sutanu STOC '21: "Near-Optimal Learning of Tree-Structured ..."
Ghaffari, Mohsen STOC '21: "Hop-Constrained Oblivious ..."
Gharan, Shayan Oveis STOC '21: "Log-Concave Polynomials IV: ..." STOC '21: "A (Slightly) Improved Approximation ..."
Ghazi, Badih STOC '21: "Sample-Efficient Proper PAC ..."
Ghoshal, Suprovat STOC '21: "Hardness of Learning DNFs ..."
Giakkoupis, George STOC '21: "Efficient Randomized DCAS ..."
Gilyén, András STOC '21: "(Sub)Exponential Advantage ..."
Giv, Mehrdad Jafari STOC '21: "Efficient Randomized DCAS ..."
Goldberg, Paul W. STOC '21: "The Complexity of Gradient ..."
Golowich, Noah STOC '21: "Sample-Efficient Proper PAC ..."
Gonen, Alon STOC '21: "Boosting Simple Learners ..."
Göös, Mika STOC '21: "Automating Algebraic Proof ..."
Gottlieb, Lee-Ad STOC '21: "Near-Linear Time Approximation ..."
Gouleakis, Themis STOC '21: "Optimal Testing of Discrete ..."
Groenland, Carla STOC '21: "Optimal Labelling Schemes ..."
Grosof, Isaac STOC '21: "Load Balancing Guardrails: ..."
Guo, Zeyu STOC '21: "Efficient List-Decoding with ..."
Gupta, Anupam STOC '21: "Chasing Convex Bodies with ..." STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
Guruganesh, Guru STOC '21: "Chasing Convex Bodies with ..."
Gurvits, Leonid STOC '21: "Capacity Lower Bounds via ..."
Haah, Jeongwan STOC '21: "Fiber Bundle Codes: Breaking ..."
Haeupler, Bernhard STOC '21: "Tree Embeddings for Hop-Constrained ..." STOC '21: "Hop-Constrained Oblivious ..." STOC '21: "Universally-Optimal Distributed ..."
Halldórsson, Magnús M. STOC '21: "Efficient Randomized Distributed ..."
Hanneke, Steve STOC '21: "A Theory of Universal Learning ..."
Harchol-Balter, Mor STOC '21: "Load Balancing Guardrails: ..."
Harms, Nathaniel STOC '21: "VC Dimension and Distribution-Free ..."
Harsha, Prahladh STOC '21: "Decoding Multivariate Multiplicity ..."
Hartline, Jason D. STOC '21: "Revelation Gap for Pricing ..."
Hastings, Matthew B. STOC '21: "(Sub)Exponential Advantage ..." STOC '21: "Fiber Bundle Codes: Breaking ..."
Hazan, Elad STOC '21: "Boosting Simple Learners ..."
Hązła, Jan STOC '21: "On Codes Decoding a Constant ..."
He, Kun STOC '21: "Sampling Constraint Satisfaction ..."
Hershkowitz, D. Ellis STOC '21: "Tree Embeddings for Hop-Constrained ..."
Hirahara, Shuichi STOC '21: "Average-Case Hardness of NP ..."
Hollender, Alexandros STOC '21: "The Complexity of Gradient ..."
Holmgren, Justin STOC '21: "Fiat–Shamir via List-Recoverable ..."
Hongler, Clément STOC '21: "Neural Tangent Kernel: Convergence ..."
Hrubes, Pavel STOC '21: "Learnability Can Be Independent ..."
Huang, Zhiyi STOC '21: "Online Stochastic Matching, ..."
Husić, Edin STOC '21: "Approximating Nash Social ..."
Jacot, Arthur STOC '21: "Neural Tangent Kernel: Convergence ..."
Jain, Aayush STOC '21: "Indistinguishability Obfuscation ..."
Jain, Vishesh STOC '21: "Perfectly Sampling k ..."
Janczewski, Wojciech STOC '21: "Fully Dynamic Approximation ..."
Jansen, Bart M. P. STOC '21: "Vertex Deletion Parameterized ..."
Jawale, Ruta STOC '21: "SNARGs for Bounded Depth Computations ..."
Jayaram, Rajesh STOC '21: "A Polynomial-Time Approximation ..." STOC '21: "When Is Approximate Counting ..."
Jeronimo, Fernando Granha STOC '21: "Near-Linear Time Decoding ..."
Jia, He STOC '21: "Reducing Isotropy and Volume ..."
Jiang, Shunhua STOC '21: "A Faster Algorithm for Solving ..."
Jung, Christopher STOC '21: "A New Analysis of Differential ..."
Kalai, Yael Tauman STOC '21: "SNARGs for Bounded Depth Computations ..."
Kandiros, Anthimos Vardis STOC '21: "Learning Ising Models from ..."
Kane, Daniel M. STOC '21: "Optimal Testing of Discrete ..." STOC '21: "Efficiently Learning Halfspaces ..."
Kapralov, Michael STOC '21: "Towards Tight Bounds for Spectral ..."
Karlin, Anna R. STOC '21: "A (Slightly) Improved Approximation ..."
Kaufman, Tali STOC '21: "New Cosystolic Expanders from ..."
Keller, Nathan STOC '21: "Local Concentration Inequalities ..."
Kelley, Zander STOC '21: "An Improved Derandomization ..."
Khot, Subhash STOC '21: "Optimal Inapproximability ..."
Khurana, Dakshita STOC '21: "SNARGs for Bounded Depth Computations ..."
Kim, Isaac H. STOC '21: "The Ghost in the Radiation: ..."
Kim, Michael P. STOC '21: "Outcome Indistinguishability ..."
Kingsford, Carl STOC '21: "How Much Data Is Sufficient ..."
Klein, Nathan STOC '21: "A (Slightly) Improved Approximation ..."
Klein, Ohad STOC '21: "Local Concentration Inequalities ..."
Klein, Philip N. STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..."
Kleinberg, Jon STOC '21: "Simplicity Creates Inequity: ..."
Knop, Alexander STOC '21: "Statistical Query Complexity ..." STOC '21: "Log-Rank and Lifting for AND-Functions ..."
Knudsen, Jakob Bæk Tejs STOC '21: "Load Balancing with Dynamic ..."
Kociumaka, Tomasz STOC '21: "Improved Dynamic Algorithms ..."
Kol, Gillat STOC '21: "Optimal Error Resilience of ..." STOC '21: "Almost Optimal Super-Constant-Pass ..."
Kontonis, Vasilis STOC '21: "Efficiently Learning Halfspaces ..."
Kothari, Pravesh K. STOC '21: "Playing Unique Games on Certified ..."
Kothari, Robin STOC '21: "Degree vs. Approximate Degree ..."
Krauthgamer, Robert STOC '21: "Towards Tight Bounds for Spectral ..." STOC '21: "Subcubic Algorithms for Gomory–Hu ..."
Krishnamurthy, Akshay STOC '21: "Contextual Search in the Presence ..."
Kuhn, Fabian STOC '21: "Efficient Randomized Distributed ..."
Kumar, Mrinal STOC '21: "Decoding Multivariate Multiplicity ..."
Kumar, Ravi STOC '21: "Sample-Efficient Proper PAC ..."
Kuszmaul, William STOC '21: "How Asymmetry Helps Buffer ..."
Laddha, Aditi STOC '21: "Reducing Isotropy and Volume ..."
Langley, Zachary STOC '21: "A Framework for Dynamic Matching ..."
Lazos, Philip STOC '21: "Efficient Two-Sided Markets ..."
Le, Hung STOC '21: "Clan Embeddings into Trees, ..."
Leake, Jonathan STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..." STOC '21: "Capacity Lower Bounds via ..."
Lee, Euiwoong STOC '21: "A Framework for Quadratic ..."
Lee, Yin Tat STOC '21: "Minimum Cost Flows, MDPs, ..." STOC '21: "Reducing Isotropy and Volume ..." STOC '21: "A Nearly-Linear Time Algorithm ..."
Leme, Renato Paes STOC '21: "Combinatorial Bernoulli Factories: ..."
Leonardi, Stefano STOC '21: "Efficient Two-Sided Markets ..." STOC '21: "Flow Time Scheduling with ..."
Levin, Leonid A. STOC '21: "Climbing Algorithms (Invited ..."
Li, Jason STOC '21: "Deterministic Mincut in Almost-Linear ..." STOC '21: "A Quasipolynomial (2 + ε)-Approximation ..." STOC '21: "Approximate Gomory–Hu Tree ..." STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
Li, Ray STOC '21: "Settling SETH vs. Approximate ..."
Li, Yingkai STOC '21: "Revelation Gap for Pricing ..."
Ligett, Katrina STOC '21: "A New Analysis of Differential ..."
Lin, Bingkai STOC '21: "Constant Approximating k-Clique ..."
Lin, Huijia STOC '21: "Indistinguishability Obfuscation ..."
Liu, Allen STOC '21: "Settling the Robust Learnability ..."
Liu, Kuikui STOC '21: "Optimal Mixing of Glauber ..." STOC '21: "Log-Concave Polynomials IV: ..."
Liu, Yang P. STOC '21: "Minimum Cost Flows, MDPs, ..." STOC '21: "Discrepancy Minimization via ..."
Liu, Yanyi STOC '21: "Cryptography from Sublinear-Time ..."
Lokshtanov, Daniel STOC '21: "Finding Large Induced Sparse ..."
Lombardi, Alex STOC '21: "Fiat–Shamir via List-Recoverable ..."
Lovett, Shachar STOC '21: "Log-Rank and Lifting for AND-Functions ..."
Lu, Zhenjian STOC '21: "Pseudodeterministic Algorithms ..."
Lykouris, Thodoris STOC '21: "Contextual Search in the Presence ..."
Lyu, Xin STOC '21: "Inverse-Exponential Correlation ..."
Mangoubi, Oren STOC '21: "Greedy Adversarial Equilibrium: ..."
Manurangsi, Pasin STOC '21: "Sample-Efficient Proper PAC ..."
Maus, Yannic STOC '21: "Efficient Randomized Distributed ..."
McGuire, Sam STOC '21: "Log-Rank and Lifting for AND-Functions ..."
McKenzie, Theo STOC '21: "Support of Closed Walks and ..."
McSwiggen, Colin STOC '21: "Sampling Matrices from Harish-Chandra–Itzykson–Zuber ..."
Minzer, Dor STOC '21: "New Separations Results for ..."
Moitra, Ankur STOC '21: "Settling the Robust Learnability ..." STOC '21: "Algorithmic Foundations for ..."
Moran, Shay STOC '21: "Learnability Can Be Independent ..." STOC '21: "A Theory of Universal Learning ..." STOC '21: "Boosting Simple Learners ..." STOC '21: "Adversarial Laws of Large ..."
Moshkovitz, Guy STOC '21: "Structure vs. Randomness for ..."
Mossel, Elchanan STOC '21: "Robust Testing of Low Dimensional ..."
Mukhopadhyay, Partha STOC '21: "Lower Bounds for Monotone ..."
Mukhopadhyay, Sagnik STOC '21: "Distributed Weighted Min-Cut ..." STOC '21: "Breaking the Quadratic Barrier ..."
Mullainathan, Sendhil STOC '21: "Simplicity Creates Inequity: ..."
N, Vishvajeet STOC '21: "Graph Streaming Lower Bounds ..."
Nakos, Vasileios STOC '21: "Sparse Nonnegative Convolution ..."
Nanongkai, Danupon STOC '21: "Distributed Weighted Min-Cut ..." STOC '21: "Breaking the Quadratic Barrier ..." STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
Naor, Assaf STOC '21: "A Framework for Quadratic ..."
Naor, Moni STOC '21: "Adversarial Laws of Large ..."
Nederlof, Jesper STOC '21: "Improving Schroeppel and Shamir’s ..."
Neel, Seth STOC '21: "A New Analysis of Differential ..."
Neeman, Joe STOC '21: "Robust Testing of Low Dimensional ..."
Nekrich, Yakov STOC '21: "Dynamic Planar Point Location ..."
Niazadeh, Rad STOC '21: "Combinatorial Bernoulli Factories: ..."
Nisan, Noam STOC '21: "Bipartite Perfect Matching ..."
Nordström, Jakob STOC '21: "Automating Algebraic Proof ..."
Nowicki, Krzysztof STOC '21: "A Deterministic Algorithm ..."
O'Donnell, Ryan STOC '21: "Improved Quantum Data Analysis ..." STOC '21: "Fiber Bundle Codes: Breaking ..."
Oliveira, Igor C. STOC '21: "Pseudodeterministic Algorithms ..."
Oshman, Rotem STOC '21: "The Communication Complexity ..."
Pan, Qinxuan STOC '21: "Sample-Optimal and Efficient ..."
Panigrahi, Debmalya STOC '21: "Approximate Gomory–Hu Tree ..." STOC '21: "Vertex Connectivity in Poly-logarithmic ..."
Paramonov, Dmitry STOC '21: "Almost Optimal Super-Constant-Pass ..."
Parisi, Daniel STOC '21: "Entropy Decay in the Swendsen–Wang ..."
Pass, Rafael STOC '21: "Cryptography from Sublinear-Time ..." STOC '21: "Indistinguishability Obfuscation ..."
Peebles, John STOC '21: "Optimal Testing of Discrete ..."
Peleg, Shir STOC '21: "Polynomial Time Deterministic ..."
Peri, Noam STOC '21: "Expander Random Walks: A Fourier-Analytic ..."
Perkins, Will STOC '21: "Frozen 1-RSB Structure of ..."
Pettie, Seth STOC '21: "Information Theoretic Limits ..."
Pich, Ján STOC '21: "Strong Co-nondeterministic ..."
Pilipczuk, Marcin STOC '21: "Finding Large Induced Sparse ..."
Pilipczuk, Michał STOC '21: "Finding Large Induced Sparse ..."
Pitassi, Toniann STOC '21: "Automating Algebraic Proof ..."