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 ..."
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 ..."
Kothari, Pravesh K. STOC '24: "Sum-of-Squares Lower Bounds ..." STOC '24: "An Exponential Lower Bound ..."
Koucký, Michal STOC '24: "Almost Linear Size Edit Distance ..."
Kozma, László STOC '24: "Optimization with Pattern-Avoiding ..."
Kretschmer, William STOC '24: "Improved Stabilizer Estimation ..."
Kreutzer, Stephan STOC '24: "Packing Even Directed Circuits ..." STOC '24: "Edge-Disjoint Paths in Eulerian ..."
Kuhn, Fabian STOC '24: "No Distributed Quantum Advantage ..."
Kulkarni, Janardhan STOC '24: "Optimal Online Discrepancy ..."
Kumar, Vinayak M. STOC '24: "Relaxed Local Correctability ..."
Kuszmaul, William STOC '24: "Space Lower Bounds for Dynamic ..."
Kyng, Rasmus STOC '24: "Almost-Linear Time Algorithms ..." STOC '24: "A Dynamic Shortest Paths Toolbox: ..."
Landau, Zeph STOC '24: "Learning Shallow Quantum Circuits ..."
Lee, Euiwoong STOC '24: "Understanding the Cluster ..." STOC '24: "Approximating Small Sparse ..."
Lee, James R. STOC '24: "Sparsifying Generalized Linear ..."
Lee, Yin Tat STOC '24: "Improving the Bit Complexity ..."
Le Gall, François STOC '24: "No Distributed Quantum Advantage ..."
Leonardi, Stefano STOC '24: "The Role of Transparency in ..."
Li, Huan STOC '24: "Detecting Low-Degree Truncation ..."
Li, Jason STOC '24: "Hypergraph Unreliability in ..." STOC '24: "Approximating Small Sparse ..." STOC '24: "Low-Step Multi-commodity Flow ..."
Li, Jerry STOC '24: "An Optimal Tradeoff between ..."
Li, Jian STOC '24: "On Optimal Coreset Construction ..."
Li, Jiatu STOC '24: "Hardness of Range Avoidance ..."
Li, Qian STOC '24: "A New Information Complexity ..."
Li, Ray STOC '24: "Randomly Punctured Reed–Solomon ..."
Li, Shi STOC '24: "Understanding the Cluster ..."
Li, Wenzheng STOC '24: "A Constant-Factor Approximation ..."
Li, Yuhao STOC '24: "Computing a Fixed Point of ..."
Li, Zeyong STOC '24: "Symmetric Exponential Time ..."
Lian, Jiayi STOC '24: "A Nearly Quadratic-Time FPTAS ..." STOC '24: "Approximating Partition in ..."
Liang, Daniel STOC '24: "Improved Stabilizer Estimation ..."
Liaw, Christopher STOC '24: "The Power of Two-Sided Recruitment ..."
Lievonen, Henrik STOC '24: "No Distributed Quantum Advantage ..."
Lifshitz, Noam STOC '24: "Product Mixing in Compact ..." STOC '24: "Influences in Mixing Measures ..."
Limaye, Nutan STOC '24: "Functional Lower Bounds in ..." STOC '24: "On the Power of Homogeneous ..."
Lin, Bingkai STOC '24: "Parameterized Inapproximability ..."
Liu, Allen STOC '24: "An Optimal Tradeoff between ..." STOC '24: "Learning Quantum Hamiltonians ..."
Liu, Chih-Hung STOC '24: "Private Graphon Estimation ..."
Liu, Sihan STOC '24: "Super Non-singular Decompositions ..." STOC '24: "Testing Closeness of Multivariate ..."
Liu, Yang P. STOC '24: "Almost-Linear Time Algorithms ..." STOC '24: "Sparsifying Generalized Linear ..."
Liu, Yinchen STOC '24: "Classical Simulation of Peaked ..."
Liu, Yunchao STOC '24: "Learning Shallow Quantum Circuits ..."
Lokshtanov, Daniel STOC '24: "Maximum Weight Independent ..."
Lolck, David Rasmussen STOC '24: "Combinatorial Correlation ..."
Lombardi, Alex STOC '24: "SNARGs under LWE via Propositional ..." STOC '24: "A One-Query Lower Bound for ..."
Lovett, Shachar STOC '24: "Explicit Separations between ..." STOC '24: "New Graph Decompositions and ..."
Lucier, Brendan STOC '24: "Strategic Budget Selection ..."
Ma, Fermi STOC '24: "A One-Query Lower Bound for ..."
Ma, Will STOC '24: "Random-Order Contention Resolution ..."
MacRury, Calum STOC '24: "Random-Order Contention Resolution ..."
Mahdavi, Mohammad STOC '24: "Prize-Collecting Steiner Tree: ..."
Mählmann, Nikolas STOC '24: "Flip-Breakability: A Combinatorial ..."
Makarychev, Yury STOC '24: "Near-Optimal Streaming Ellipsoidal ..."
Manohar, Peter STOC '24: "An Exponential Lower Bound ..."
Manoj, Naren Sarayu STOC '24: "Near-Optimal Streaming Ellipsoidal ..."
Mao, Xiao STOC '24: "Fully Dynamic All-Pairs Shortest ..." STOC '24: "(1 − 𝜀)-Approximation ..."
Mao, Yuchen STOC '24: "A Nearly Quadratic-Time FPTAS ..." STOC '24: "Approximating Partition in ..."
Marx, Dániel STOC '24: "Counting Small Induced Subgraphs ..."
Masařík, Tomáš STOC '24: "Maximum Weight Independent ..."
Mastel, Kieran STOC '24: "Two Prover Perfect Zero Knowledge ..."
Mathialagan, Surya STOC '24: "Towards Optimal Output-Sensitive ..."
Mátravölgyi, Bence STOC '24: "Reconfiguration of Basis Pairs ..."
McClean, Jarrod R. STOC '24: "Learning Shallow Quantum Circuits ..."
McKenzie, Theo STOC '24: "Explicit Two-Sided Unique-Neighbor ..."
Mehraban, Saeed STOC '24: "Quadratic Lower Bounds on ..."
Mehta, Aranyak STOC '24: "The Power of Two-Sided Recruitment ..."
Meierhans, Simon STOC '24: "Almost-Linear Time Algorithms ..." STOC '24: "A Dynamic Shortest Paths Toolbox: ..."
Meka, Raghu STOC '24: "Explicit Separations between ..." STOC '24: "New Graph Decompositions and ..."
Mertz, Ian STOC '24: "Tree Evaluation Is in Space ..."
Minzer, Dor STOC '24: "Product Mixing in Compact ..." STOC '24: "On Approximability of Satisfiable ..." STOC '24: "Near Optimal Alphabet-Soundness ..." STOC '24: "Characterizing Direct Product ..." STOC '24: "Influences in Mixing Measures ..."
Mirrokni, Vahab STOC '24: "Optimal Communication Bounds ..."
Modanese, Augusto STOC '24: "No Distributed Quantum Advantage ..."
Mohanty, Sidhanth STOC '24: "Robust Recovery for Stochastic ..." STOC '24: "Explicit Two-Sided Unique-Neighbor ..."
Moitra, Ankur STOC '24: "Learning Quantum Hamiltonians ..." STOC '24: "Exploring and Learning in ..."
Molinaro, Marco STOC '24: "Supermodular Approximation ..."
Mon, Geoffrey STOC '24: "Relaxed Local Correctability ..."
Montanaro, Ashley STOC '24: "Quantum and Classical Query ..."
Moran, Shay STOC '24: "Local Borsuk-Ulam, Stability, ..."
Mossel, Elchanan STOC '24: "A Unified Approach to Learning ..." STOC '24: "Influences in Mixing Measures ..."
Mukhopadhyay, Partha STOC '24: "Black-Box Identity Testing ..."
Nadimpalli, Shivam STOC '24: "Detecting Low-Degree Truncation ..." STOC '24: "Optimal Non-adaptive Tolerant ..." STOC '24: "On the Pauli Spectrum of QAC0 ..."
Naidu, Kheeran K. STOC '24: "O(log log n) Passes Is Optimal ..."
Nanashima, Mikito STOC '24: "One-Way Functions and Zero ..."
Narayan, Vishnu V. STOC '24: "Fair Division via Quantile ..."
Natura, Bento STOC '24: "A Strongly Polynomial Algorithm ..."
Newman, Alantha STOC '24: "Understanding the Cluster ..."
Newman, Ilan STOC '24: "Hardness Condensation by Restriction ..."
Ng, Hiu Tsun STOC '24: "How Random CSPs Fool Hierarchies ..."
Nguyen, Quynh T. STOC '24: "Circuit-to-Hamiltonian from ..."
Niazadeh, Rad STOC '24: "Prophet Inequalities with ..."
Nogler, Jakob STOC '24: "On the Communication Complexity ..."
Nusser, André STOC '24: "Minimum Star Partitions of ..."
Nuti, Pranav STOC '24: "Prophet Inequalities with ..."
O'Connor, Jack STOC '24: "Perfect Zero-Knowledge PCPs ..."
Ohsaka, Naoto STOC '24: "Probabilistically Checkable ..."
Oliveira, Rafael STOC '24: "Strong Algebras and Radical ..."
Olver, Neil STOC '24: "A Strongly Polynomial Algorithm ..."
Opler, Michal STOC '24: "Optimization with Pattern-Avoiding ..."
Ostuni, Anthony STOC '24: "Locality Bounds for Sampling ..."
Ovsiankin, Max STOC '24: "Near-Optimal Streaming Ellipsoidal ..."
Padmanabhan, Swati STOC '24: "Improving the Bit Complexity ..."
Pak, Igor STOC '24: "Equality Cases of the Alexandrov–Fenchel ..."
Paneth, Omer STOC '24: "Batch Proofs Are Statistically ..."
Panigrahi, Debmalya STOC '24: "Hypergraph Unreliability in ..."
Paraashar, Manaswi STOC '24: "Local Correction of Linear ..."
Paredes, Pedro STOC '24: "Explicit Two-Sided Unique-Neighbor ..."
Parekh, Ojas STOC '24: "Exponential Quantum Space ..."
Parham, Natalie STOC '24: "On the Pauli Spectrum of QAC0 ..."
Parter, Merav STOC '24: "Connectivity Labeling and ..."
Patel, Neel STOC '24: "Limitations of Stochastic ..."
Patel, Shyamal STOC '24: "Optimal Non-adaptive Tolerant ..." STOC '24: "Distribution-Free Testing ..." STOC '24: "Polylog-Competitive Deterministic ..."
Pegden, Wesley STOC '24: "Sampling Balanced Forests ..."
Peng, Binghui STOC '24: "Fast Swap Regret Minimization ..."
Peng, Sijin STOC '24: "How Random CSPs Fool Hierarchies ..."
Petruschka, Asaf STOC '24: "Connectivity Labeling and ..."
Pettie, Seth STOC '24: "Connectivity Labeling and ..."
Pilipczuk, Marcin STOC '24: "Combinatorial Correlation ..." STOC '24: "Maximum Weight Independent ..."
Pilipczuk, Michał STOC '24: "Maximum Weight Independent ..."
Pitassi, Toniann STOC '24: "Black-Box PPP Is Not Turing-Closed ..."
Potechin, Aaron STOC '24: "Sum-of-Squares Lower Bounds ..."
Pratt, Kevin STOC '24: "A Stronger Connection between ..."
Preskill, John STOC '24: "Local Minima in Quantum Systems ..."
Probst Gutenberg, Maximilian STOC '24: "Almost-Linear Time Algorithms ..." STOC '24: "A Dynamic Shortest Paths Toolbox: ..."
Pyne, Edward STOC '24: "Opening Up the Distinguisher: ..."
Qian, Luowen STOC '24: "An Efficient Quantum Parallel ..."
Qiu, Frederick STOC '24: "Settling the Communication ..."
Raghavendra, Prasad STOC '24: "Robust Recovery for Stochastic ..."
Rajgopal, Ninad STOC '24: "On the Power of Interactive ..."
Rao, Anup STOC '24: "XOR Lemmas for Communication ..."
Reis, Victor STOC '24: "Optimal Online Discrepancy ..."
Ren, Hanlin STOC '24: "Symmetric Exponential Time ..."
Ren, Xuandi STOC '24: "Parameterized Inapproximability ..."
Renou, Marc-Olivier STOC '24: "Nonlocality under Computational ..." STOC '24: "No Distributed Quantum Advantage ..."
Riazanov, Artur STOC '24: "Hardness Condensation by Restriction ..."
Robere, Robert STOC '24: "Black-Box PPP Is Not Turing-Closed ..."
Roeyskoe, Antti STOC '24: "Low-Step Multi-commodity Flow ..." STOC '24: "Polylog-Competitive Deterministic ..."
Roghani, Mohammad STOC '24: "Approximating Maximum Matching ..."
Rohatgi, Dhruv STOC '24: "Exploring and Learning in ..."
Rossman, Benjamin STOC '24: "Formula Size-Depth Tradeoffs ..."
Rothblum, Ron D. STOC '24: "Batch Proofs Are Statistically ..."
Rothvoss, Thomas STOC '24: "Optimal Online Discrepancy ..."
Roughgarden, Tim STOC '24: "The Computer in the Sky (Keynote) ..."
Rubinstein, Aviad STOC '24: "Fast Swap Regret Minimization ..." STOC '24: "Approximating Maximum Matching ..." STOC '24: "A Constant-Factor Approximation ..." STOC '24: "Approximate Earth Mover’s ..." STOC '24: "Parallel Sampling via Counting ..."
Rudelson, Mark STOC '24: "Optimal Embedding Dimension ..."
Rzążewski, Paweł STOC '24: "Maximum Weight Independent ..."
Sahami, Arvin STOC '24: "Explicit Orthogonal Arrays ..."
Saks, Michael E. STOC '24: "Almost Linear Size Edit Distance ..."
Salamatian, Bahar STOC '24: "On the Power of Interactive ..."
Saran, Nitika STOC '24: "Breaking the VLB Barrier for ..."
Saranurak, Thatchaphol STOC '24: "Approximating Small Sparse ..." STOC '24: "Low-Step Multi-commodity Flow ..."
Savani, Rahul STOC '24: "The Complexity of Computing ..."
Saxena, Nitin STOC '24: "Learning the Coefficients: ..."
Schmid, Gustav STOC '24: "No Distributed Quantum Advantage ..."
Schramm, Tselil STOC '24: "Semidefinite Programs Simulate ..."
Schwarcz, Tamás STOC '24: "Reconfiguration of Basis Pairs ..."
Sengupta, Akash Kumar STOC '24: "Strong Algebras and Radical ..."
Servedio, Rocco A. STOC '24: "Detecting Low-Degree Truncation ..."
Seth, Cameron STOC '24: "New Graph and Hypergraph Container ..."
Shaltiel, Ronen STOC '24: "Explicit Codes for Poly-Size ..."
Shao, Changpeng STOC '24: "Quantum and Classical Query ..."
Shaulker, Ariel STOC '24: "Bilateral Trade with Correlated ..."
Shimizu, Nobutaka STOC '24: "Planted Clique Conjectures ..."
Shinkar, Igor STOC '24: "On the Power of Interactive ..."
Shrivastav, Vishal STOC '24: "Breaking the VLB Barrier for ..."
Sidford, Aaron STOC '24: "Sparsifying Generalized Linear ..." STOC '24: "Near-Optimal Dynamic Rounding ..."
Silbak, Jad STOC '24: "Explicit Codes for Poly-Size ..."
Sinclair, Alistair STOC '24: "Nonlinear Dynamics for the ..."
Singla, Sahil STOC '24: "Supermodular Approximation ..."
Sinha, Makrand STOC '24: "The Power of Adaptivity in ..."
Slivkins, Aleksandrs STOC '24: "Strategic Budget Selection ..."
Slofstra, William STOC '24: "Two Prover Perfect Zero Knowledge ..."
Sly, Allan STOC '24: "Local Geometry of NAE-SAT ..."
Sohn, Youngtak STOC '24: "Local Geometry of NAE-SAT ..."
Sokolov, Dmitry STOC '24: "Random (log 𝑛)-CNF Are ..." STOC '24: "Hardness Condensation by Restriction ..."
Sokołowski, Marek STOC '24: "Almost-Linear Time Parameterized ..."
Spooner, Nicholas STOC '24: "An Efficient Quantum Parallel ..." STOC '24: "Perfect Zero-Knowledge PCPs ..."
Srinivas, Vaidehi STOC '24: "New Tools for Smoothed Analysis: ..."
Srinivasan, Srikanth STOC '24: "On the Power of Homogeneous ..." STOC '24: "Local Correction of Linear ..."
Stehlé, Damien STOC '24: "Quantum Oblivious LWE Sampling ..."
Stein, Cliff STOC '24: "Polylog-Competitive Deterministic ..."
Steurer, David STOC '24: "Private Graphon Estimation ..."
Sudan, Madhu STOC '24: "Local Correction of Linear ..."
Sun, Yican STOC '24: "Parameterized Inapproximability ..."
Sundaresan, Janani STOC '24: "O(log log n) Passes Is Optimal ..."
Suomela, Jukka STOC '24: "No Distributed Quantum Advantage ..."
Svensson, Ola STOC '24: "Online Edge Coloring Is (Nearly) ..."
Swartworth, William STOC '24: "Improving the Bit Complexity ..."
Tahmasbi, Mehrdad STOC '24: "Quadratic Lower Bounds on ..."
Tal, Avishay STOC '24: "The Power of Adaptivity in ..."
Tang, Ewin STOC '24: "Learning Quantum Hamiltonians ..."
Tavenas, Sébastien STOC '24: "On the Power of Homogeneous ..."
Tell, Roei STOC '24: "Opening Up the Distinguisher: ..."
Thakkar, Dhara STOC '24: "The Minimal Faithful Permutation ..."
Thomas, Clayton STOC '24: "Structural Complexities of ..."
Thorup, Mikkel STOC '24: "Combinatorial Correlation ..." STOC '24: "Better Coloring of 3-Colorable ..."
Tomer, Kabir STOC '24: "Commitments from Quantum One-Wayness ..."
Toruńczyk, Szymon STOC '24: "Flip-Breakability: A Combinatorial ..."
Tucker-Foltz, Jamie STOC '24: "Sampling Balanced Forests ..."
Tzameret, Iddo STOC '24: "Functional Lower Bounds in ..."
Vadhan, Salil STOC '24: "Complexity-Theoretic Implications ..."
Vafa, Neekon STOC '24: "Memory Checking Requires Logarithmic ..."
Vaikuntanathan, Vinod STOC '24: "Quantum State Obfuscation ..." STOC '24: "SNARGs under LWE via Propositional ..."
Valiant, Gregory STOC '24: "Near-Optimal Mean Estimation ..."
Vasconcelos, Francisca STOC '24: "On the Pauli Spectrum of QAC0 ..."
Vasudevan, Prashant Nalini STOC '24: "Batch Proofs Are Statistically ..."
Végh, László A. STOC '24: "A Strongly Polynomial Algorithm ..."
Vempala, Santosh S. STOC '24: "Calibrated Language Models ..."
Vijayaraghavan, Aravindan STOC '24: "New Tools for Smoothed Analysis: ..."
Vintan, Radu STOC '24: "Online Edge Coloring Is (Nearly) ..."
Vogl, Lukas STOC '24: "Understanding the Cluster ..."
Vondrák, Jan STOC '24: "Prophet Inequalities with ..." STOC '24: "A Constant-Factor Approximation ..."
Voronova, Nadezhda STOC '24: "Exponential Quantum Space ..."
Vuong, Thuy-Duong STOC '24: "Trickle-Down in Localization ..."
Waingarten, Erik STOC '24: "Data-Dependent LSH for the ..."
Wajc, David STOC '24: "Online Edge Coloring Is (Nearly) ..." STOC '24: "Near-Optimal Dynamic Rounding ..."
Walzer, Stefan STOC '24: "Space Lower Bounds for Dynamic ..."
Wang, Brandon STOC '24: "Lenzen’s Distributed Routing ..."
Wang, Hanzhi STOC '24: "Revisiting Local Computation ..."
Wang, Shuo STOC '24: "A New Information Complexity ..."
Wang, Yulin STOC '24: "Sampling Proper Colorings ..."
Waters, Brent STOC '24: "Adaptively-Sound Succinct ..." STOC '24: "A New Approach for Non-Interactive ..."
Weatherspoon, Hakim STOC '24: "Breaking the VLB Barrier for ..."
Wei, Zhewei STOC '24: "Revisiting Local Computation ..."
Weinberg, S. Matthew STOC '24: "Settling the Communication ..."
Wellnitz, Philip STOC '24: "Counting Small Induced Subgraphs ..." STOC '24: "On the Communication Complexity ..."
Wen, Ji-Rong STOC '24: "Revisiting Local Computation ..."
Whitmeyer, Michael STOC '24: "Quantum Time-Space Tradeoffs ..."
Wiederrecht, Sebastian STOC '24: "Packing Even Directed Circuits ..." STOC '24: "A Flat Wall Theorem for Matching ..."
Williams, R. Ryan STOC '24: "Self-Improvement for Circuit-Analysis ..." STOC '24: "Beating Brute Force for Compression ..."
Williams, Virginia Vassilevska STOC '24: "Towards Optimal Output-Sensitive ..."
Wilson, Tegan STOC '24: "Breaking the VLB Barrier for ..."
Woodruff, David P. STOC '24: "Improving the Bit Complexity ..." STOC '24: "A New Information Complexity ..." STOC '24: "Optimal Communication Bounds ..."
Wright, John STOC '24: "A One-Query Lower Bound for ..."
Wu, David J. STOC '24: "Adaptively-Sound Succinct ..."
Wu, David X. STOC '24: "Robust Recovery for Stochastic ..."
Wu, Kewen STOC '24: "Locality Bounds for Sampling ..." STOC '24: "The Power of Adaptivity in ..." STOC '24: "Parameterized Inapproximability ..."
Wu, Xuan STOC '24: "On Optimal Coreset Construction ..."
Xie, Zhiye STOC '24: "Tight Time-Space Tradeoffs ..."
Xu, Jeff STOC '24: "Sum-of-Squares Lower Bounds ..."
Xu, Yinzhan STOC '24: "Shaving Logs via Large Sieve ..." STOC '24: "Towards Optimal Output-Sensitive ..."
Yan, Shuyi STOC '24: "Combinatorial Correlation ..."
Yang, Guangxu STOC '24: "Communication Lower Bounds ..."
Yang, Jiaming STOC '24: "Solving Dense Linear Systems ..."
Yang, Mingji STOC '24: "Revisiting Local Computation ..."
Yannakakis, Mihalis STOC '24: "Computing a Fixed Point of ..."
Ye, Guanghao STOC '24: "Improving the Bit Complexity ..."
Ye, Yuping STOC '24: "Tight Time-Space Tradeoffs ..."
Yehudayoff, Amir STOC '24: "Local Borsuk-Ulam, Stability, ..."
Yoneda, Hirotaka STOC '24: "Better Coloring of 3-Colorable ..."
Yuen, Henry STOC '24: "An Efficient Quantum Parallel ..." STOC '24: "On the Pauli Spectrum of QAC0 ..."
Zarifis, Nikos STOC '24: "Super Non-singular Decompositions ..."
Zenklusen, Rico STOC '24: "Ghost Value Augmentation for ..."
Zhang, Chihao STOC '24: "Sampling Proper Colorings ..."
Zhang, Guochuan STOC '24: "A Nearly Quadratic-Time FPTAS ..." STOC '24: "Approximating Partition in ..."
Zhang, Hanwen STOC '24: "Combinatorial Correlation ..." STOC '24: "Minimum Star Partitions of ..."
Zhang, Jiapeng STOC '24: "A New Information Complexity ..." STOC '24: "Communication Lower Bounds ..."
Zhang, Tian STOC '24: "Data-Dependent LSH for the ..."
Zhang, Zhijun STOC '24: "Optimal Multi-pass Lower Bounds ..."
Zhang, Zihan STOC '24: "Sampling Proper Colorings ..." STOC '24: "AG Codes Achieve List Decoding ..."
Zhao, Mingfei STOC '24: "The Power of Two-Sided Recruitment ..."
Zheng, Kai Zhe STOC '24: "Near Optimal Alphabet-Soundness ..."
Zhong, Peilin STOC '24: "Optimal Communication Bounds ..."
Zhou, Leo STOC '24: "Local Minima in Quantum Systems ..."
Ziliotto, Bruno STOC '24: "Prophet Inequalities Require ..."
Živný, Stanislav STOC '24: "Semidefinite Programming and ..."
Zuzic, Goran STOC '24: "Polylog-Competitive Deterministic ..."

582 authors

proc time: 127.22