STOCTheoretical Computer Science
ACM Symposium on Theory of Computing
2020 - 2025Website
Recent papers
- A (2+ε)-Approximation Algorithm for Metric k-MedianVincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn et al. · 2025 · 1 citation
- A 5/4-Approximation for Two-Edge ConnectivityMiguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim et al. · 2025 · 9 citations
- A Bound on the Quantum Value of All Compiled Nonlocal GamesAlexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt et al. · 2025 · 4 citations
- A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and FriendsKarl Bringmann, Egor Gorbachev · 2025 · 5 citations
- A Framework for Building Data Structures from Communication ProtocolsAlexandr Andoni, Shunhua Jiang, Omri Weinstein · 2025
- A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and FireJohn Bostanci, Barak Nehoran, Mark Zhandry · 2025 · 2 citations
- A Generalized Trace Reconstruction Problem: Recovering a String of ProbabilitiesJoey Rivkin, Gregory Valiant, Paul Valiant · 2025 · 1 citation
- A New Approach for LPN-Based Pseudorandom Functions: Low-Depth and Key-HomomorphicYoulong Ding, Aayush Jain, Ilan Komargodski · 2025 · 3 citations
- A Sharp Version of Talagrand's Selector Process Conjecture and an Application to Rounding Fractional CoversHuy Tuan Pham · 2025 · 1 citation
- A Tolerant Independent Set TesterCameron Seth · 2025 · 1 citation
- A Zero-Knowledge PCP TheoremTom Gur, Jack O'Connor, Nicholas Spooner · 2025 · 1 citation
- Accelerated Approximate Optimization of Multi-commodity Flows on Directed GraphsLi Chen, Andrei Graur, Aaron Sidford · 2025 · 1 citation
- Adaptive and Oblivious Statistical Adversaries Are EquivalentGuy Blanc, Gregory Valiant · 2025 · 1 citation
- Adaptive Approximation Schemes for Matching QueuesAlireza AmaniHamedani, Ali Aouad, Amin Saberi · 2025 · 4 citations
- Agnostic Smoothed Online LearningMoïse Blanchard · 2025 · 4 citations
- All-Pairs Shortest Paths with Few Weights per NodeAmir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams et al. · 2025
- Almost Optimal PAC Learning for k-MeansVincent Cohen-Addad, Silvio Lattanzi, Chris Schwiegelshohn · 2025
- Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETHVenkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun et al. · 2025 · 3 citations
- Approximately Counting and Sampling Hamiltonian Motifs in Sublinear TimeTalya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld · 2025
- Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic DepthZhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai · 2025 · 1 citation
- Approximation Algorithms for the Geometric Multimatching ProblemShinwoo An, Eunjin Oh, Jie Xue · 2025 · 1 citation
- Approximation Guarantees of Median Mechanism in ℝᵈNikolai Gravin, Jianhao Jia · 2025 · 1 citation
- Asymptotic Tensor Rank Is Characterized by PolynomialsMatthias Christandl, Koen Hoeberechts, Harold Nieuwboer, Péter Vrana et al. · 2025 · 2 citations
- Asymptotically Good Quantum Codes with Transversal Non-Clifford GatesLouis Golowich, Venkatesan Guruswami · 2025 · 2 citations