💀 The Wall of Shame

The most cited papers with no code. Sorted by the weight of their sins.

Page 2, showing 50 papers

# Paper Cause of Death Category Citations Published
51 A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
👻 Ghosted cs.DC 112 10 years ago
52 Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time
Danupon Nanongkai, Thatchaphol Saranurak
👻 Ghosted cs.DS 107 9 years ago
53 Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time
Christian Wulff-Nilsen
👻 Ghosted cs.DS 104 9 years ago
54 Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, ... (+5 more)
👻 Ghosted cs.DS 104 9 years ago
55 Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev, Lap Chi Lau
👻 Ghosted cs.DS 103 6 years ago
56 Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, ... (+4 more)
👻 Ghosted cs.DS 103 8 years ago
57 Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, ... (+2 more)
👻 Ghosted cs.DS 100 6 years ago
58 Quantum state certification
Costin Bădescu, Ryan O'Donnell, John Wright
👻 Ghosted quant-ph 100 8 years ago
59 New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
👻 Ghosted cs.DS 100 10 years ago
60 Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia
👻 Ghosted cs.LG 96 10 years ago
61 Lossy Kernelization
Daniel Lokshtanov, Fahad Panolan, ... (+2 more)
👻 Ghosted cs.DS 95 10 years ago
62 Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
👻 Ghosted cs.LG 94 8 years ago
63 An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
Yin Tat Lee, He Sun
👻 Ghosted cs.DS 92 9 years ago
64 Bipartite Perfect Matching is in quasi-NC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
🔮 The Ethereal cs.CC 91 10 years ago
65 The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
John Fearnley, Paul W. Goldberg, ... (+2 more)
🔮 The Ethereal cs.CC 90 5 years ago
66 k-server via multiscale entropic regularization
Sebastien Bubeck, Michael B. Cohen, ... (+3 more)
👻 Ghosted cs.DS 90 8 years ago
67 Online and Dynamic Algorithms for Set Cover
Anupam Gupta, Ravishankar Krishnaswamy, ... (+2 more)
👻 Ghosted cs.DS 89 9 years ago
68 Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, ... (+3 more)
👻 Ghosted cs.DS 88 8 years ago
69 Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Bernhard Haeupler, Amirbehshad Shahrasbi
👻 Ghosted cs.IT 88 9 years ago
70 Strongly Refuting Random CSPs Below the Spectral Threshold
Prasad Raghavendra, Satish Rao, Tselil Schramm
👻 Ghosted cs.DS 88 9 years ago
71 How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, Alexander S. Wein
👻 Ghosted cs.DS 87 10 years ago
72 The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, ... (+3 more)
👻 Ghosted cs.DS 86 7 years ago
73 An Optimal Distributed $(Δ+1)$-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
👻 Ghosted cs.DC 86 8 years ago
74 Uniform Sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum, Jingcheng Liu
👻 Ghosted cs.DS 86 9 years ago
75 Beating 1-1/e for Ordered Prophets
Melika Abolhasani, Soheil Ehsani, ... (+4 more)
👻 Ghosted cs.DS 85 9 years ago
76 Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
Lingxiao Huang, Nisheeth K. Vishnoi
👻 Ghosted cs.CG 83 6 years ago
77 How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, ... (+4 more)
👻 Ghosted cs.DS 83 8 years ago
78 Uniformly bounded regret in the multi-secretary problem
Alessandro Arlotto, Itai Gurvich
👻 Ghosted math.PR 82 8 years ago
79 Online Matching: Haste makes Waste!
Yuval Emek, Shay Kutten, Roger Wattenhofer
👻 Ghosted cs.DS 81 10 years ago
80 Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu, Aaron Sidford
👻 Ghosted cs.DS 79 6 years ago
81 Distributed Exact Shortest Paths in Sublinear Time
Michael Elkin
👻 Ghosted cs.DS 79 9 years ago
82 Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
🔮 The Ethereal cs.CC 78 9 years ago
83 Optimal mean-based algorithms for trace reconstruction
Anindya De, Ryan O'Donnell, Rocco Servedio
🔮 The Ethereal cs.CC 77 9 years ago
84 Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, ... (+3 more)
👻 Ghosted cs.DS 76 9 years ago
85 The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, ... (+2 more)
👻 Ghosted cs.DS 75 8 years ago
86 Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples
Fedor Nazarov, Yuval Peres
👻 Ghosted math.PR 75 9 years ago
87 Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula, Vahab Mirrokni, Morteza Zadimoghaddam
👻 Ghosted cs.DS 74 8 years ago
88 Robustly Learning Mixtures of $k$ Arbitrary Gaussians
Ainesh Bakshi, Ilias Diakonikolas, ... (+4 more)
👻 Ghosted cs.DS 72 5 years ago
89 Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, ... (+2 more)
👻 Ghosted cs.DS 72 8 years ago
90 The Computational Power of Optimization in Online Learning
Elad Hazan, Tomer Koren
👻 Ghosted cs.LG 72 11 years ago
91 A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
Haris Aziz, Simon Mackenzie
👻 Ghosted cs.DS 72 10 years ago
92 A Theory of Universal Learning
Olivier Bousquet, Steve Hanneke, ... (+3 more)
👻 Ghosted cs.LG 71 5 years ago
93 An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild
👻 Ghosted cs.DS 70 8 years ago
94 The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman
👻 Ghosted cs.DS 69 6 years ago
95 Quadratic speedup for finding marked vertices by quantum walks
Andris Ambainis, András Gilyén, ... (+2 more)
👻 Ghosted quant-ph 69 7 years ago
96 Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal
👻 Ghosted cs.DS 69 11 years ago
97 Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
👻 Ghosted cs.DS 68 10 years ago
98 String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa, Tomasz Kociumaka
👻 Ghosted cs.DS 66 7 years ago
99 Robust Linear Regression: Optimal Rates in Polynomial Time
Ainesh Bakshi, Adarsh Prasad
👻 Ghosted stat.ML 63 5 years ago
100 Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
👻 Ghosted cs.DS 63 6 years ago