STOC 2024
56th Annual ACM Symposium on Theory of Computing (STOC 2024)
Powered by
Conference Publishing Consulting

56th Annual ACM Symposium on Theory of Computing (STOC 2024), June 24–28, 2024, Vancouver, BC, Canada

STOC 2024 – Author Index

Contents - Abstracts - Authors

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

Abboud, Amir STOC '24: "New Graph Decompositions and ..."
Abrahamsen, Mikkel STOC '24: "Minimum Star Partitions of ..."
Ahmadi, Ali STOC '24: "Prize-Collecting Steiner Tree: ..."
Akshima STOC '24: "Tight Time-Space Tradeoffs ..."
Alrabiah, Omar STOC '24: "Randomly Punctured Reed–Solomon ..."
Amir, Daniel STOC '24: "Breaking the VLB Barrier for ..."
Amireddy, Prashanth STOC '24: "Local Correction of Linear ..."
Anand, Aditya STOC '24: "Approximating Small Sparse ..."
Anari, Nima STOC '24: "Trickle-Down in Localization ..." STOC '24: "Parallel Sampling via Counting ..."
Anshu, Anurag STOC '24: "Learning Shallow Quantum Circuits ..." STOC '24: "Circuit-to-Hamiltonian from ..."
Arad, Itai STOC '24: "An Area Law for the Maximally-Mixed ..."
Arvind, V. STOC '24: "Black-Box Identity Testing ..."
Assadi, Sepehr STOC '24: "O(log log n) Passes Is Optimal ..." STOC '24: "Optimal Multi-pass Lower Bounds ..."
Babichenko, Yakov STOC '24: "Fair Division via Quantile ..."
Bafna, Mitali STOC '24: "Characterizing Direct Product ..."
Bakshi, Ainesh STOC '24: "Learning Quantum Hamiltonians ..."
Bangachev, Kiril STOC '24: "On the Fourier Coefficients ..."
Barooti, Khashayar STOC '24: "Nonlocality under Computational ..."
Bartusek, James STOC '24: "Quantum State Obfuscation ..."
Beame, Paul STOC '24: "Quantum Time-Space Tradeoffs ..."
Behera, Amik Raj STOC '24: "Local Correction of Linear ..."
Behnezhad, Soheil STOC '24: "Approximating Maximum Matching ..."
Bérczi, Kristóf STOC '24: "Reconfiguration of Basis Pairs ..."
Berendsohn, Benjamin Aram STOC '24: "Optimization with Pattern-Avoiding ..."
Beretta, Lorenzo STOC '24: "Approximate Earth Mover’s ..."
Bergamaschi, Thiago STOC '24: "Approaching the Quantum Singleton ..."
Bernasconi, Martino STOC '24: "No-Regret Learning in Bilateral ..."
Besselman, Tyler STOC '24: "Tight Time-Space Tradeoffs ..."
Bhangale, Amey STOC '24: "On Approximability of Satisfiable ..."
Bhargav, C. S. STOC '24: "Learning the Coefficients: ..."
Bhaskara, Aditya STOC '24: "New Tools for Smoothed Analysis: ..."
Bhattacharya, Sayan STOC '24: "Near-Optimal Dynamic Rounding ..."
Bitansky, Nir STOC '24: "Batch Proofs Are Statistically ..."
Björklund, Andreas STOC '24: "The Asymptotic Rank Conjecture ..."
Blais, Eric STOC '24: "New Graph and Hypergraph Container ..."
Blikstad, Joakim STOC '24: "Minimum Star Partitions of ..." STOC '24: "Online Edge Coloring Is (Nearly) ..."
Bostanci, John STOC '24: "An Efficient Quantum Parallel ..."
Boyle, Elette STOC '24: "Memory Checking Requires Logarithmic ..."
Brakensiek, Joshua STOC '24: "Generalized GM-MDS: Polynomial ..." STOC '24: "AG Codes Achieve List Decoding ..."
Brakerski, Zvika STOC '24: "Quantum State Obfuscation ..."
Braverman, Mark STOC '24: "A New Information Complexity ..."
Bravyi, Sergey STOC '24: "Classical Simulation of Peaked ..."
Bresler, Guy STOC '24: "On the Fourier Coefficients ..."
Breuckmann, Nikolas P. STOC '24: "Circuit-to-Hamiltonian from ..."
Bringmann, Karl STOC '24: "Knapsack with Small Items ..."
Broughton, Michael STOC '24: "Learning Shallow Quantum Circuits ..."
Buchbinder, Niv STOC '24: "Constrained Submodular Maximization ..."
Cai, Yang STOC '24: "The Power of Two-Sided Recruitment ..."
Cannon, Sarah STOC '24: "Sampling Balanced Forests ..."
Cao, Nairen STOC '24: "Understanding the Cluster ..."
Caputo, Pietro STOC '24: "Nonlinear Dynamics for the ..."
Casacuberta, Sílvia STOC '24: "Complexity-Theoretic Implications ..."
Castiglioni, Matteo STOC '24: "No-Regret Learning in Bilateral ..."
Cavallaro, Dario Giuliano STOC '24: "Edge-Disjoint Paths in Eulerian ..."
Celli, Andrea STOC '24: "No-Regret Learning in Bilateral ..."
Cen, Ruoxu STOC '24: "Hypergraph Unreliability in ..."
Cesa-Bianchi, Nicolo STOC '24: "The Role of Transparency in ..."
Cesari, Tommaso STOC '24: "The Role of Transparency in ..."
Chan, Siu On STOC '24: "How Random CSPs Fool Hierarchies ..."
Chan, Swee Hong STOC '24: "Equality Cases of the Alexandrov–Fenchel ..."
Chase, Zachary STOC '24: "Local Borsuk-Ulam, Stability, ..."
Chatterjee, Abhranil STOC '24: "Black-Box Identity Testing ..."
Chenakkod, Shabarish STOC '24: "Optimal Embedding Dimension ..."
Chen, Chi-Fang STOC '24: "Local Minima in Quantum Systems ..."
Chen, Hongjie STOC '24: "Private Graphon Estimation ..."
Chen, Li STOC '24: "Almost-Linear Time Algorithms ..."
Chen, Lijie STOC '24: "Symmetric Exponential Time ..."
Chen, Lin STOC '24: "A Nearly Quadratic-Time FPTAS ..." STOC '24: "Approximating Partition in ..."
Chen, Sitan STOC '24: "An Optimal Tradeoff between ..."
Chen, Xi STOC '24: "Computing a Fixed Point of ..." STOC '24: "Distribution-Free Testing ..."
Chen, Yilei STOC '24: "Hardness of Range Avoidance ..."
Chornomaz, Bogdan STOC '24: "Local Borsuk-Ulam, Stability, ..."
Chuzhoy, Julia STOC '24: "Maximum Bipartite Matching ..."
Ciardo, Lorenzo STOC '24: "Semidefinite Programming and ..."
Cohen-Addad, Vincent STOC '24: "Understanding the Cluster ..." STOC '24: "Combinatorial Correlation ..."
Coiteux-Roy, Xavier STOC '24: "No Distributed Quantum Advantage ..."
Coladangelo, Andrea STOC '24: "How to Use Quantum Indistinguishability ..."
Colomboni, Roberto STOC '24: "The Role of Transparency in ..."
Compton, Spencer STOC '24: "Near-Optimal Mean Estimation ..."
Cook, James STOC '24: "Tree Evaluation Is in Space ..."
Cristi, Andrés STOC '24: "Prophet Inequalities Require ..."
Dadush, Daniel STOC '24: "A Strongly Polynomial Algorithm ..."
Dagan, Yuval STOC '24: "From External to Swap Regret ..."
Dalirrooyfard, Mina STOC '24: "Towards Optimal Output-Sensitive ..."
D'Amore, Francesco STOC '24: "No Distributed Quantum Advantage ..."
Das, Bireswar STOC '24: "The Minimal Faithful Permutation ..."
Daskalakis, Constantinos STOC '24: "From External to Swap Regret ..."
De, Anindya STOC '24: "Detecting Low-Degree Truncation ..."
Debris-Alazard, Thomas STOC '24: "Quantum Oblivious LWE Sampling ..."
Dereziński, Michał STOC '24: "Optimal Embedding Dimension ..." STOC '24: "Solving Dense Linear Systems ..."
Dey, Dipan STOC '24: "Nearly Optimal Fault Tolerant ..."
Dhar, Manik STOC '24: "Generalized GM-MDS: Polynomial ..." STOC '24: "AG Codes Achieve List Decoding ..."
Diakonikolas, Ilias STOC '24: "Super Non-singular Decompositions ..." STOC '24: "Testing Closeness of Multivariate ..."
Dikstein, Yotam STOC '24: "Agreement Theorems for High ..." STOC '24: "Swap Cosystolic Expansion ..."
Ding, Jingqiu STOC '24: "Private Graphon Estimation ..."
Dinur, Irit STOC '24: "Agreement Theorems for High ..." STOC '24: "Swap Cosystolic Expansion ..."
Dobzinski, Shahar STOC '24: "A Constant-Factor Approximation ..." STOC '24: "Bilateral Trade with Correlated ..."
Dong, Ruiwen STOC '24: "Semigroup Algorithmic Problems ..."
Dong, Xiaoyu STOC '24: "Optimal Embedding Dimension ..."
Döring, Simon STOC '24: "Counting Small Induced Subgraphs ..."
Doron, Dean STOC '24: "Opening Up the Distinguisher: ..."
D'Orsi, Tommaso STOC '24: "Private Graphon Estimation ..."
Dreier, Jan STOC '24: "Flip-Breakability: A Combinatorial ..."
Dughmi, Shaddin STOC '24: "Limitations of Stochastic ..."
Dwivedi, Prateek STOC '24: "Learning the Coefficients: ..."
Dwork, Cynthia STOC '24: "Complexity-Theoretic Implications ..."
Efremenko, Klim STOC '24: "Lower Bounds for Regular Resolution ..."
Ekbatani, Farbod STOC '24: "Prophet Inequalities with ..."
Ellis, David STOC '24: "Product Mixing in Compact ..."
Esfandiari, Hossein STOC '24: "Optimal Communication Bounds ..."
Evert, Eric STOC '24: "New Tools for Smoothed Analysis: ..."
Fallahpour, Pouria STOC '24: "Quantum Oblivious LWE Sampling ..."
Fang, Yuting STOC '24: "No Complete Problem for Constant-Cost ..."
Fearnley, John STOC '24: "The Complexity of Computing ..."
Fei, Yumou STOC '24: "Distribution-Free Testing ..."
Feldman, Michal STOC '24: "Fair Division via Quantile ..." STOC '24: "Algorithmic Contract Design ..."
Feldman, Moran STOC '24: "Constrained Submodular Maximization ..."
Feng, Yiding STOC '24: "Strategic Budget Selection ..."
Filos-Ratsikas, Aris STOC '24: "PPAD-Membership for Problems ..."
Fineman, Jeremy T. STOC '24: "Single-Source Shortest Paths ..."
Firanko, Raz STOC '24: "An Area Law for the Maximally-Mixed ..."
First, Uriya A. STOC '24: "Cosystolic Expansion of Sheaves ..."
Fischer, Nick STOC '24: "New Graph Decompositions and ..."
Fishelson, Maxwell STOC '24: "From External to Swap Regret ..."
Fleming, Noah STOC '24: "Black-Box PPP Is Not Turing-Closed ..."
Fournier, Hervé STOC '24: "On the Power of Homogeneous ..."
Fusco, Federico STOC '24: "No-Regret Learning in Bilateral ..." STOC '24: "The Role of Transparency in ..."
Gaitonde, Jason STOC '24: "A Unified Approach to Learning ..."
Gajjala, Rishikesh STOC '24: "No Distributed Quantum Advantage ..."
Gao, Ruiquan STOC '24: "Parallel Sampling via Counting ..."
Garg, Sumegha STOC '24: "A New Information Complexity ..."
Garlík, Michal STOC '24: "Lower Bounds for Regular Resolution ..."
Gartland, Peter STOC '24: "Maximum Weight Independent ..."
Gelles, Yuval STOC '24: "Optimal Load-Balanced Scalable ..."
Ghadiri, Mehrdad STOC '24: "Improving the Bit Complexity ..."
Ghaffari, Mohsen STOC '24: "Lenzen’s Distributed Routing ..." STOC '24: "Work-Efficient Parallel Derandomization ..." STOC '24: "Dynamic O(Arboricity) Coloring ..."
Gheorghiu, Alexandru STOC '24: "Nonlocality under Computational ..."
Gholami, Iman STOC '24: "Prize-Collecting Steiner Tree: ..."
Giannopoulou, Archontia C. STOC '24: "A Flat Wall Theorem for Matching ..."
Girish, Uma STOC '24: "The Power of Adaptivity in ..."
Gluch, Grzegorz STOC '24: "Nonlocality under Computational ..."
Goldberg, Paul W. STOC '24: "The Complexity of Computing ..."
Golowich, Louis STOC '24: "Approaching the Quantum Singleton ..."
Golowich, Noah STOC '24: "Exploring and Learning in ..." STOC '24: "From External to Swap Regret ..."
Gonczarowski, Yannai A. STOC '24: "Structural Complexities of ..."
Göös, Mika STOC '24: "Hardness Condensation by Restriction ..."
Gopi, Sivakanth STOC '24: "Generalized GM-MDS: Polynomial ..." STOC '24: "AG Codes Achieve List Decoding ..."
Gorsky, Maximilian STOC '24: "Packing Even Directed Circuits ..."
Gosset, David STOC '24: "Classical Simulation of Peaked ..."
Grewal, Sabee STOC '24: "Improved Stabilizer Estimation ..."
Grosser, Stefan STOC '24: "Black-Box PPP Is Not Turing-Closed ..."
Grunau, Christoph STOC '24: "Work-Efficient Parallel Derandomization ..." STOC '24: "Dynamic O(Arboricity) Coloring ..."
Gunn, Sam STOC '24: "How to Use Quantum Indistinguishability ..." STOC '24: "Approaching the Quantum Singleton ..."
Guo, Siyao STOC '24: "Tight Time-Space Tradeoffs ..."
Gupta, Manoj STOC '24: "Nearly Optimal Fault Tolerant ..."
Gupta, Meghal STOC '24: "Constant Query Local Decoding ..."
Gur, Tom STOC '24: "Perfect Zero-Knowledge PCPs ..." STOC '24: "On the Power of Interactive ..."
Guruswami, Venkatesan STOC '24: "Randomly Punctured Reed–Solomon ..." STOC '24: "Parameterized Inapproximability ..."
Haeupler, Bernhard STOC '24: "Polylog-Competitive Deterministic ..." STOC '24: "Low-Step Multi-commodity Flow ..."
Hajiaghayi, MohammadTaghi STOC '24: "Prize-Collecting Steiner Tree: ..."
Hakoniemi, Tuomas STOC '24: "Functional Lower Bounds in ..."
Hambardzumyan, Lianna STOC '24: "No Complete Problem for Constant-Cost ..."
Hansen, Kristoffer Arnsfelt STOC '24: "PPAD-Membership for Problems ..."
Harms, Nathaniel STOC '24: "No Complete Problem for Constant-Cost ..."
Harvey, Nicholas STOC '24: "Explicit Orthogonal Arrays ..."
Hatami, Pooya STOC '24: "No Complete Problem for Constant-Cost ..."
Hershkowitz, D. Ellis STOC '24: "Ghost Value Augmentation for ..." STOC '24: "Low-Step Multi-commodity Flow ..."
Hirahara, Shuichi STOC '24: "One-Way Functions and Zero ..." STOC '24: "Probabilistically Checkable ..." STOC '24: "Planted Clique Conjectures ..." STOC '24: "Beating Brute Force for Compression ..." STOC '24: "Symmetric Exponential Time ..."
Høgh, Kasper STOC '24: "PPAD-Membership for Problems ..."
Hollender, Alexandros STOC '24: "The Complexity of Computing ..." STOC '24: "PPAD-Membership for Problems ..."
Holzman, Ron STOC '24: "Fair Division via Quantile ..."
Hsieh, Jun-Ting STOC '24: "Explicit Two-Sided Unique-Neighbor ..."
Huang, Hsin-Yuan STOC '24: "Local Minima in Quantum Systems ..." STOC '24: "Learning Shallow Quantum Circuits ..."
Huang, Lingxiao STOC '24: "On Optimal Coreset Construction ..."
Hua, Yiding STOC '24: "Private Graphon Estimation ..."
Ilango, Rahul STOC '24: "Beating Brute Force for Compression ..."
Itsykson, Dmitry STOC '24: "Lower Bounds for Regular Resolution ..."
Ivkov, Misha STOC '24: "Semidefinite Programs Simulate ..."
Iyer, Siddharth STOC '24: "XOR Lemmas for Communication ..."
Iyer, Vishnu STOC '24: "Improved Stabilizer Estimation ..."
Jabbarzade, Peyman STOC '24: "Prize-Collecting Steiner Tree: ..."
Jahanara, Mohammad Mahdi STOC '24: "On the Power of Interactive ..."
Jain, Rahul STOC '24: "An Area Law for the Maximally-Mixed ..."
Jambulapati, Arun STOC '24: "Sparsifying Generalized Linear ..."
Jayaram, Rajesh STOC '24: "Data-Dependent LSH for the ..."
Jin, Ce STOC '24: "Shaving Logs via Large Sieve ..." STOC '24: "0-1 Knapsack in Nearly Quadratic ..."
Jin, Zhengzhong STOC '24: "SNARGs under LWE via Propositional ..."
Kacham, Praneeth STOC '24: "Optimal Communication Bounds ..."
Kalai, Adam Tauman STOC '24: "Calibrated Language Models ..."
Kalai, Yael STOC '24: "SNARGs under LWE via Propositional ..."
Kalayci, Yusuf Hakan STOC '24: "Limitations of Stochastic ..."
Kallaugher, John STOC '24: "Exponential Quantum Space ..."
Kamath, Chethan STOC '24: "Batch Proofs Are Statistically ..."
Kane, Daniel M. STOC '24: "Super Non-singular Decompositions ..." STOC '24: "Testing Closeness of Multivariate ..." STOC '24: "Locality Bounds for Sampling ..."
Kaski, Petteri STOC '24: "The Asymptotic Rank Conjecture ..."
Kaufman, Tali STOC '24: "Cosystolic Expansion of Sheaves ..."
Kawamura, Akitoshi STOC '24: "Proof of the Density Threshold ..."
Kawarabayashi, Ken-ichi STOC '24: "Edge-Disjoint Paths in Eulerian ..." STOC '24: "Better Coloring of 3-Colorable ..." STOC '24: "Packing Even Directed Circuits ..."
Kelley, Zander STOC '24: "Explicit Separations between ..." STOC '24: "New Graph Decompositions and ..."
Kesselheim, Thomas STOC '24: "Supermodular Approximation ..."
Khanna, Sanjeev STOC '24: "Maximum Bipartite Matching ..."
Khodabandeh, Mohammad Mahdi STOC '24: "On the Power of Interactive ..."
Khot, Subhash STOC '24: "On Approximability of Satisfiable ..."
Khurana, Dakshita STOC '24: "Commitments from Quantum One-Wayness ..."
Kim, Isaac STOC '24: "Learning Shallow Quantum Circuits ..."
Kindler, Guy STOC '24: "Product Mixing in Compact ..."
Kiss, Peter STOC '24: "Near-Optimal Dynamic Rounding ..."
Kleinberg, Robert STOC '24: "Breaking the VLB Barrier for ..."
Klein, Nathan STOC '24: "Ghost Value Augmentation for ..."
Kociumaka, Tomasz STOC '24: "On the Communication Complexity ..."
Koehler, Frederic STOC '24: "Trickle-Down in Localization ..." STOC '24: "Influences in Mixing Measures ..."
Koh, Zhuan Khye STOC '24: "A Strongly Polynomial Algorithm ..."
Kol, Gillat STOC '24: "Optimal Multi-pass Lower Bounds ..."
Komargodski, Ilan STOC '24: "Memory Checking Requires Logarithmic ..." STOC '24: "Optimal Load-Balanced Scalable ..."
Konrad, Christian STOC '24: "O(log log n) Passes Is Optimal ..."
Kontonis, Vasilis STOC '24: "Super Non-singular Decompositions ..."
Korhonen, Tuukka STOC '24: "Almost-Linear Time Parameterized ..."
Kornerup, Niels STOC '24: "Quantum Time-Space Tradeoffs ..."