🏠
홈
📊
트렌드
🏆
논문
👤
마이
💬 문의
CS-
Pedia
Trends
Best Papers
Best Papers
/
STOC
STOC Best Papers
ACM Symposium on Theory of Computing
14 papers · 2020–2025
← STOC Conference Info
🏆
2025
(3)
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
🏆
2024
(3)
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
🏆
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