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: "Optimal Multi-pass Lower Bounds ..." STOC '24: "O(log log n) Passes Is Optimal ..."
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: "Online Edge Coloring Is (Nearly) ..." STOC '24: "Minimum Star Partitions of ..."
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 ..."
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: "Distribution-Free Testing ..." STOC '24: "Computing a Fixed Point of ..."
Chen, Yilei STOC '24: "Hardness of Range Avoidance ..."
Chenakkod, Shabarish STOC '24: "Optimal Embedding Dimension ..."
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: "Swap Cosystolic Expansion ..." STOC '24: "Agreement Theorems for High ..."
Ding, Jingqiu STOC '24: "Private Graphon Estimation ..."
Dinur, Irit STOC '24: "Swap Cosystolic Expansion ..." STOC '24: "Agreement Theorems for High ..."
Dobzinski, Shahar STOC '24: "Bilateral Trade with Correlated ..." STOC '24: "A Constant-Factor Approximation ..."
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: "The Role of Transparency in ..." STOC '24: "No-Regret Learning in Bilateral ..."
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: "Dynamic O(Arboricity) Coloring ..." STOC '24: "Lenzen’s Distributed Routing ..." STOC '24: "Work-Efficient Parallel Derandomization ..."
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: "From External to Swap Regret ..." STOC '24: "Exploring and Learning in ..."
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: "Dynamic O(Arboricity) Coloring ..." STOC '24: "Work-Efficient Parallel Derandomization ..."
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: "On the Power of Interactive ..." STOC '24: "Perfect Zero-Knowledge PCPs ..."
Guruswami, Venkatesan STOC '24: "Randomly Punctured Reed–Solomon ..." STOC '24: "Parameterized Inapproximability ..."
Haeupler, Bernhard STOC '24: "Low-Step Multi-commodity Flow ..." STOC '24: "Polylog-Competitive Deterministic ..."
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: "Probabilistically Checkable ..." STOC '24: "One-Way Functions and Zero ..." STOC '24: "Symmetric Exponential Time ..." STOC '24: "Planted Clique Conjectures ..." STOC '24: "Beating Brute Force for Compression ..."
Høgh, Kasper STOC '24: "PPAD-Membership for Problems ..."
Hollender, Alexandros STOC '24: "PPAD-Membership for Problems ..." STOC '24: "The Complexity of Computing ..."
Holzman, Ron STOC '24: "Fair Division via Quantile ..."
Hsieh, Jun-Ting STOC '24: "Explicit Two-Sided Unique-Neighbor ..."
Hua, Yiding STOC '24: "Private Graphon Estimation ..."
Huang, Hsin-Yuan STOC '24: "Local Minima in Quantum Systems ..." STOC '24: "Learning Shallow Quantum Circuits ..."
Huang, Lingxiao STOC '24: "On Optimal Coreset Construction ..."
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: "Locality Bounds for Sampling ..." STOC '24: "Super Non-singular Decompositions ..." STOC '24: "Testing Closeness of Multivariate ..."
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: "Better Coloring of 3-Colorable ..." STOC '24: "Packing Even Directed Circuits ..." STOC '24: "Edge-Disjoint Paths in Eulerian ..."
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 ..."
Klein, Nathan STOC '24: "Ghost Value Augmentation for ..."
Kleinberg, Robert STOC '24: "Breaking the VLB Barrier for ..."
Kociumaka, Tomasz STOC '24: "On the Communication Complexity ..."