🏠
홈
📊
트렌드
🏆
논문
👤
마이
💬 문의
CS-
Pedia
Trends
Best Papers
Best Papers
/
STOC
STOC Best Papers
ACM Symposium on Theory of Computing
23 papers · 2020–2026
← STOC Conference Info
🏆
2026
(5)
Best Paper Award
Lower Estimates for L_1-Distortion of Transportation Cost Spaces
Chris Gartland; Mikhail Ostrovskii
Best Paper Award
Separating QMA from QCMA with a classical oracle
John Bostanci; Jonas Haferkamp; Chinmay Nirkhe; Mark Zhandry
Best Paper Award
Boolean function monotonicity testing requires (almost) n^1/2 queries
Mark Chen; Xi Chen; Hao Cui; William Pires; Jonah Stockwell
Best Student Paper Award
NP-membership for the boundary-boundary art-gallery problem
Jack Stade
Best Student Paper Award
MIP^co = coRE
Junqiao (Randy) Lin
🏆
2025
(5)
Best Paper Award
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran DuanJiayi MaoXiao MaoXinkai ShuLonghui Yin
algorithms
graph algorithms
shortest paths
Best Paper Award
Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
Yeyuan ChenZihan Zhang
coding theory
error-correcting codes
complexity theory
Best Paper Award
Vizing's Theorem in Near-Linear Time
Sepehr AssadiSoheil BehnezhadSayan BhattacharyaMartín CostaShay SolomonTianyi Zhang
algorithms
graph theory
edge coloring
Best Paper Award
Simulating Time with Square-Root Space
R. Ryan Williams
Computational Complexity
Best Paper Award
Quasi-Linear Size PCPs with Small Soundness from HDX
Mitali Bafna, Dor Minzer, Nikhil Vyas, Zhiwei Yun
🏆
2024
(5)
Best Paper Award
Single-Source Shortest Paths with Negative Real Weights in Õ(mn^{8/9}) Time
Fineman
Shortest Paths
Graph Algorithms
Best Paper Award
Near Optimal Alphabet-Soundness Tradeoff PCPs
Minzer & Zheng
PCP
Complexity Theory
Best Paper Award
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Guruswami, Lin, Ren, Sun & Wu
Parameterized Complexity
Inapproximability
Best Paper Award
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin & Yinzhan Xu
Sparse Methods
Best Paper Award
Relaxed Local Correctability from Local Testing
Vinayak M. Kumar & Geoffrey Mon
🏆
2023
(2)
Best Paper Award
The Randomized k-Server Conjecture Is False!
Bubeck et al.
k-Server
Online Algorithms
Best Paper Award
Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
Wei Kai Lin, Ethan Mook, Daniel Wichs
Information Retrieval
Efficiency
Homomorphic Encryption
🏆
2022
(2)
Best Paper Award
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
Pavel PanteleevGleb Kalachev
quantum computing
coding theory
error-correcting codes
Best Paper Award
Locally Testable Codes with Constant Rate, Distance, and Locality
Irit DinurShai EvraRon LivneAlexander LubotzkyShahar Mozes
coding theory
error-correcting codes
complexity theory
🏆
2021
(3)
Best Paper Award
A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. KarlinNathan KleinShayan Oveis Gharan
algorithms
approximation
traveling salesman
combinatorial optimization
Best Paper Award
Indistinguishability Obfuscation from Well-Founded Assumptions
Aayush JainHuijia LinAmit Sahai
cryptography
obfuscation
hardness assumptions
Best Paper Award
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
John FearnleyPaul W. GoldbergAlexandros HollenderRahul Savani
complexity theory
gradient descent
algorithms
🏆
2020
(1)
Best Paper Award
Improved Bounds for The Sunflower Lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zheng