STOC

Publications

2024

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
Local Correction of Linear Functions over the Boolean Cube. STOC (2024)
Zachary Chase, Bogdan Chornomaz, Shay Moran, Amir Yehudayoff
Local Borsuk-Ulam, Stability, and Replicability. STOC (2024)
John Kallaugher, Ojas Parekh, Nadezhda Voronova
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. STOC (2024)
William Kuszmaul, Stefan Walzer
Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval. STOC (2024)
Michal Feldman
Algorithmic Contract Design (Keynote). STOC (2024)
Mohsen Ghaffari, Christoph Grunau
Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time. STOC (2024)
Saeed Mehraban, Mehrdad Tahmasbi
Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach. STOC (2024)
Ruoxu Cen, Jason Li, Debmalya Panigrahi
Hypergraph Unreliability in Quasi-Polynomial Time. STOC (2024)
Siu On Chan, Hiu Tsun Ng, Sijin Peng
How Random CSPs Fool Hierarchies. STOC (2024)
Jeremy T. Fineman
Time. STOC (2024)
Lorenzo Ciardo, Stanislav Zivný
Semidefinite Programming and Linear Equations vs. Homomorphism Problems. STOC (2024)
Yotam Dikstein, Irit Dinur
Swap Cosystolic Expansion. STOC (2024)
Janardhan Kulkarni, Victor Reis, Thomas Rothvoss
Optimal Online Discrepancy Minimization. STOC (2024)
Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel
Limitations of Stochastic Selection Problems with Pairwise Independent Priors. STOC (2024)
Frederic Koehler, Noam Lifshitz, Dor Minzer, Elchanan Mossel
Influences in Mixing Measures. STOC (2024)
Kristóf Bérczi, Bence Mátravölgyi, Tamás Schwarcz
Reconfiguration of Basis Pairs in Regular Matroids. STOC (2024)
Vinayak M. Kumar, Geoffrey Mon
Relaxed Local Correctability from Local Testing. STOC (2024)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. STOC (2024)
Yang Cai, Christopher Liaw, Aranyak Mehta, Mingfei Zhao
The Power of Two-Sided Recruitment in Two-Sided Markets. STOC (2024)
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. STOC (2024)
Benjamin Rossman
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. STOC (2024)
Grzegorz Gluch, Khashayar Barooti, Alexandru Gheorghiu, Marc-Olivier Renou
Nonlocality under Computational Assumptions. STOC (2024)
Kevin Pratt
A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture. STOC (2024)
Zhengzhong Jin, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan
SNARGs under LWE via Propositional Proofs. STOC (2024)
Tim Roughgarden
The Computer in the Sky (Keynote). STOC (2024)
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes. STOC (2024)
Andrés Cristi, Bruno Ziliotto
Prophet Inequalities Require Only a Constant Number of Samples. STOC (2024)
Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak
Low-Step Multi-commodity Flow Emulators. STOC (2024)
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi
Prize-Collecting Steiner Tree: A 1.79 Approximation. STOC (2024)
Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, Jarrod R. McClean
Learning Shallow Quantum Circuits. STOC (2024)
Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen
Circuit-to-Hamiltonian from Tensor Networks and Fault Tolerance. STOC (2024)
Simon Döring, Dániel Marx, Philip Wellnitz
Counting Small Induced Subgraphs with Edge-Monotone Properties. STOC (2024)
Nima Anari, Frederic Koehler, Thuy-Duong Vuong
Trickle-Down in Localization Schemes and Applications. STOC (2024)
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
A Nearly Quadratic-Time FPTAS for Knapsack. STOC (2024)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. STOC (2024)
D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
Ghost Value Augmentation for k-Edge-Connectivity. STOC (2024)
Sílvia Casacuberta, Cynthia Dwork, Salil P. Vadhan
Complexity-Theoretic Implications of Multicalibration. STOC (2024)
David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer
Product Mixing in Compact Lie Groups. STOC (2024)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. STOC (2024)
Thiago Bergamaschi, Louis Golowich, Sam Gunn
Approaching the Quantum Singleton Bound with Approximate Error Correction. STOC (2024)
Binghui Peng, Aviad Rubinstein
Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. STOC (2024)
Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht
Packing Even Directed Circuits Quarter-Integrally. STOC (2024)
Nicholas Harvey, Arvin Sahami
Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters. STOC (2024)
Allan Sly, Youngtak Sohn
Local Geometry of NAE-SAT Solutions in the Condensation Regime. STOC (2024)
Rajesh Jayaram, Erik Waingarten, Tian Zhang
Data-Dependent LSH for the Earth Mover's Distance. STOC (2024)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. STOC (2024)
Nima Anari, Ruiquan Gao, Aviad Rubinstein
Parallel Sampling via Counting. STOC (2024)
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. STOC (2024)
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, Hanwen Zhang
Combinatorial Correlation Clustering. STOC (2024)
Brent Waters, David J. Wu
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation. STOC (2024)