STOCTheoretical Computer Science
ACM Symposium on Theory of Computing
1,159Papers indexed
2020-2026Years covered
Recent papers
- 3-Query RLDCs Are Strictly Stronger Than 3-Query LDCsTom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng2026 · 8 citations
- A (4+ϵ)-Approximation for Euclidean k-Means via Non-monotone Dual-FittingMoses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni et al.2026 · 3 citations
- A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge FailuresBernhard Haeupler, Yaowei Long, Antti Roeyskoe, Thatchaphol Saranurak2026
- A Constant-Factor Approximation for Directed LatencyJannis Blauth, Ramin Mousavi2026
- A Dichotomy Theorem for Multi-pass Streaming CSPsYumou Fei, Dor Minzer, Shuo Wang2026 · 11 citations
- A Dobrushin Condition for Quantum Markov Chains: Rapid Mixing and Conditional Mutual Information at High TemperatureAinesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang2026 · 13 citations
- A Faster Deterministic Algorithm for Fully Dynamic Maximal MatchingJulia Chuzhoy, Sanjeev Khanna, Junkai Song2026
- A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the HypercubeGautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan2026 · 2 citations
- A Graph Minors Approach to Temporal SequencesJohannes Carmesin, Will J. Turner2026 · 1 citation
- A Meta-complexity Characterization of Minimal Quantum CryptographyBruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray et al.2026 · 4 citations
- A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning ConjunctionsXi Chen, Shyamal Patel, Rocco A. Servedio2026 · 4 citations
- A Poisson Process for Submodular MaximizationAmit Ganz Rozenman, Ariel Kulik, Roy Schwartz, Mohit Singh2026 · 5 citations
- A Polylogarithmic Approximation for Buy-at-Bulk Network Design with ProtectionChandra Chekuri, Rhea Jain2026 · 2 citations
- A Sharp Characterization of PessilandShuichi Hirahara, Mikito Nanashima2026
- A Strong Linear Programming Relaxation for Weighted Tree AugmentationVincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson2026
- A Theory for Probabilistic Polynomial-Time ReasoningLijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams2026 · 1 citation
- A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted StructuresSumegha Garg, Jabari Hastings, Chirag Pabbaraju, Vatsal Sharan2026 · 1 citation
- A Unified Framework for Analysis of Randomized Greedy Matching AlgorithmsMahsa Derakhshan, Tao Yu2026 · 3 citations
- Adaptive Robustness of Hypergrid Johnson-LindenstraussAndrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan2026 · 1 citation
- Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time BarrierSayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang2026 · 2 citations
- Adversarial Robustness on Insertion-Deletion StreamsElena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu et al.2026 · 2 citations
- Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed GraphsRon Mosenzon2026 · 3 citations
- An Analytical Approach to Parallel Repetition via CSP Inverse TheoremsAmey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu et al.2026
- An Improved Quality Hierarchical Congestion Approximator in Near-Linear TimeMonika Henzinger, Robin Münk, Harald Räcke2026 · 4 citations
