💀 The Wall of Shame

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

Page 4, showing 50 papers

# Paper Cause of Death Category Citations Published
151 Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, ... (+2 more)
👻 Ghosted cs.DS 47 6 years ago
152 $O(\log^2k/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
👻 Ghosted cs.DS 47 7 years ago
153 Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi, Allen Liu, ... (+2 more)
👻 Ghosted quant-ph 46 2 years ago
154 Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
🔮 The Ethereal cs.CC 46 7 years ago
155 Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, ... (+3 more)
👻 Ghosted cs.DC 46 9 years ago
156 Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski
👻 Ghosted cs.GT 46 10 years ago
157 Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
👻 Ghosted cs.DS 45 7 years ago
158 Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
Chong Shangguan, Itzhak Tamo
👻 Ghosted cs.IT 45 6 years ago
159 More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, ... (+2 more)
🔮 The Ethereal cs.CC 45 7 years ago
160 Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler, Amirbehshad Shahrasbi
👻 Ghosted cs.IT 45 8 years ago
161 Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
🔮 The Ethereal cs.CC 45 9 years ago
162 Subquadratic Submodular Function Minimization
Deeparnab Chakrabarty, Yin Tat Lee, ... (+2 more)
👻 Ghosted cs.DS 45 9 years ago
163 Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, ... (+2 more)
👻 Ghosted cs.DS 45 4 years ago
164 Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu, Ankur Moitra
👻 Ghosted cs.DS 44 5 years ago
165 Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Federica Cecchetto, Vera Traub, Rico Zenklusen
👻 Ghosted cs.DS 44 5 years ago
166 Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucký, Michael E. Saks
👻 Ghosted cs.DS 44 7 years ago
167 The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas, Paul W. Goldberg
🔮 The Ethereal cs.CC 44 7 years ago
168 Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
👻 Ghosted cs.DS 44 8 years ago
169 Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
👻 Ghosted cs.LG 44 8 years ago
170 Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer, ... (+2 more)
👻 Ghosted quant-ph 43 3 years ago
171 Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, Zhao Song
👻 Ghosted cs.DS 43 6 years ago
172 Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
🔮 The Ethereal cs.DM 43 6 years ago
173 Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
👻 Ghosted cs.DS 43 8 years ago
174 The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, Shuyi Yan
👻 Ghosted cs.DS 43 4 years ago
175 Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, ... (+6 more)
👻 Ghosted cs.LG 42 3 years ago
176 A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
👻 Ghosted cs.DS 42 6 years ago
177 Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, ... (+2 more)
👻 Ghosted cs.DS 42 7 years ago
178 An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov, Dmitry Krachun
👻 Ghosted cs.DS 42 7 years ago
179 Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
👻 Ghosted cs.DS 42 7 years ago
180 Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
👻 Ghosted cs.DS 42 8 years ago
181 Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, ... (+3 more)
👻 Ghosted cs.DS 42 9 years ago
182 Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
👻 Ghosted cs.DS 41 5 years ago
183 Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng, Aviad Rubinstein
👻 Ghosted cs.GT 39 2 years ago
184 Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang, Qiankun Zhang
👻 Ghosted cs.DS 39 6 years ago
185 Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, ... (+3 more)
👻 Ghosted math.ST 39 6 years ago
186 Explicit near-Ramanujan graphs of every degree
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
👻 Ghosted cs.DS 39 6 years ago
187 Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
👻 Ghosted cs.DS 39 7 years ago
188 Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, ... (+2 more)
👻 Ghosted cs.DS 39 7 years ago
189 Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis, Martins Kokainis
👻 Ghosted quant-ph 39 9 years ago
190 Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, Rad Niazadeh
👻 Ghosted cs.DS 39 11 years ago
191 Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, ... (+2 more)
👻 Ghosted cs.DS 38 5 years ago
192 New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
👻 Ghosted cs.DS 38 6 years ago
193 Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
👻 Ghosted cs.DS 38 6 years ago
194 Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
🔮 The Ethereal cs.CC 38 6 years ago
195 Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, Andrej Risteski
👻 Ghosted cs.LG 38 7 years ago
196 Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, ... (+2 more)
👻 Ghosted cs.DS 37 5 years ago
197 Fast sampling and counting k-SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, ... (+2 more)
👻 Ghosted cs.DS 37 6 years ago
198 Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, Amin Karbasi
👻 Ghosted cs.DS 37 7 years ago
199 Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
👻 Ghosted cs.DS 37 7 years ago
200 Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen, Ankur Moitra
👻 Ghosted cs.LG 37 8 years ago