💀 The Wall of Shame

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

Page 1

# Paper Cause of Death Category Citations Published
1 Complexity Theoretic Limitations on Learning Halfspaces
Amit Daniely
🔮 The Ethereal cs.CC 146 10 years ago
2 Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Zongchen Chen, Kuikui Liu, Eric Vigoda
🔮 The Ethereal cs.DM 142 5 years ago
3 Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, ... (+2 more)
🔮 The Ethereal cs.CC 125 10 years ago
4 Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, Avi Wigderson
🔮 The Ethereal cs.CC 119 11 years ago
5 Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
🔮 The Ethereal cs.CC 112 8 years ago
6 Bipartite Perfect Matching is in quasi-NC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
🔮 The Ethereal cs.CC 91 10 years ago
7 The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
John Fearnley, Paul W. Goldberg, ... (+2 more)
🔮 The Ethereal cs.CC 90 5 years ago
8 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
9 Optimal mean-based algorithms for trace reconstruction
Anindya De, Ryan O'Donnell, Rocco Servedio
🔮 The Ethereal cs.CC 77 9 years ago
10 Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane, Ryan Williams
🔮 The Ethereal cs.CC 60 10 years ago
11 A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs, Eric Blais
🔮 The Ethereal cs.CC 54 10 years ago
12 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 6 years ago
13 Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
🔮 The Ethereal cs.CC 45 9 years ago
14 More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, ... (+2 more)
🔮 The Ethereal cs.CC 45 7 years ago
15 The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas, Paul W. Goldberg
🔮 The Ethereal cs.CC 44 7 years ago
16 Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
🔮 The Ethereal cs.DM 43 6 years ago
17 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
18 First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
🔮 The Ethereal cs.LO 34 3 years ago
19 The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
Pierre-Étienne Meunier, Damien Woods
🔮 The Ethereal cs.CC 33 9 years ago
20 An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism
Daniel Neuen, Pascal Schweitzer
🔮 The Ethereal cs.CC 33 8 years ago
21 A Converse to Banach's Fixed Point Theorem and its CLS Completeness
Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis
🔮 The Ethereal cs.CC 31 9 years ago
22 A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
🔮 The Ethereal cs.DM 28 8 years ago
23 An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen
🔮 The Ethereal cs.DM 21 6 years ago
24 On the effect of randomness on planted 3-coloring models
Roee David, Uriel Feige
🔮 The Ethereal cs.CC 16 10 years ago
25 Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin, Yinzhan Xu
🔮 The Ethereal cs.CC 16 4 years ago
26 Twenty (simple) questions
Yuval Dagan, Yuval Filmus, ... (+2 more)
🔮 The Ethereal cs.DM 15 9 years ago
27 Explicit two-sided unique-neighbor expanders
Jun-Ting Hsieh, Theo McKenzie, ... (+2 more)
🔮 The Ethereal math.CO 15 3 years ago
28 Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
🔮 The Ethereal cs.CC 14 4 years ago
29 Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Alexander S. Wein
🔮 The Ethereal cs.CC 14 3 years ago
30 A stronger connection between the asymptotic rank conjecture and the set cover conjecture
Kevin Pratt
🔮 The Ethereal cs.CC 14 2 years ago
31 Optimal labelling schemes for adjacency, comparability, and reachability
Marthe Bonamy, Louis Esperet, ... (+2 more)
🔮 The Ethereal math.CO 11 5 years ago
32 Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, ... (+7 more)
🔮 The Ethereal cs.CC 10 3 years ago
33 Sampling Balanced Forests of Grids in Polynomial Time
Sarah Cannon, Wesley Pegden, Jamie Tucker-Foltz
🔮 The Ethereal cs.DM 9 2 years ago
34 Counting Small Induced Subgraphs with Edge-monotone Properties
Simon Döring, Dániel Marx, Philip Wellnitz
🔮 The Ethereal cs.CC 9 2 years ago
35 Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný
🔮 The Ethereal cs.CC 8 2 years ago
36 On the Complexity of CSP-based Ideal Membership Problems
Andrei A. Bulatov, Akbar Rafiey
🔮 The Ethereal cs.CC 7 5 years ago
37 Local and global expansion in random geometric graphs
Siqi Liu, Sidhanth Mohanty, ... (+2 more)
🔮 The Ethereal math.CO 7 3 years ago
38 On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Joshua A. Grochow, Youming Qiao
🔮 The Ethereal cs.CC 7 2 years ago
39 Detecting Low-Degree Truncation
Anindya De, Huan Li, ... (+2 more)
🔮 The Ethereal cs.CC 7 2 years ago
40 Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet
🔮 The Ethereal cs.CC 7 1 year ago
41 On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, ... (+4 more)
🔮 The Ethereal cs.CC 6 1 year ago
42 Merge-width and First-Order Model Checking
Jan Dreier, Szymon Toruńczyk
🔮 The Ethereal math.CO 6 1 year ago
43 Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, ... (+3 more)
🔮 The Ethereal math.CO 5 1 year ago
44 Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, ... (+2 more)
🔮 The Ethereal cs.CC 5 1 year ago
45 Smoothed analysis for graph isomorphism
Michael Anastos, Matthew Kwan, Benjamin Moore
🔮 The Ethereal math.CO 4 1 year ago
46 Testing noisy linear functions for sparsity
Xue Chen, Anindya De, Rocco A. Servedio
🔮 The Ethereal cs.CC 3 6 years ago
47 Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Uriya A. First, Tali Kaufman
🔮 The Ethereal math.CO 3 2 years ago
48 A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, ... (+4 more)
🔮 The Ethereal cs.CC 3 1 year ago
49 Leakage-Resilient Extractors against Number-on-Forehead Protocols
Eshan Chattopadhyay, Jesse Goodman
🔮 The Ethereal cs.CC 1 9 months ago
50 Strong XOR Lemma for Information Complexity
Pachara Sawettamalya, Huacheng Yu
🔮 The Ethereal cs.CC 0 1 year ago