💀 The Wall of Shame

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

Page 1, showing 50 papers

# Paper Cause of Death Category Citations Published
1 Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
🔮 The Ethereal cs.CC 259 11 years ago
2 An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
🔮 The Ethereal cs.CC 177 10 years ago
3 If the Current Clique Algorithms are Optimal, so is Valiant's Parser
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
🔮 The Ethereal cs.CC 129 10 years ago
4 Which Regular Expression Patterns are Hard to Match?
Arturs Backurs, Piotr Indyk
🔮 The Ethereal cs.CC 109 10 years ago
5 How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
🔮 The Ethereal cs.CC 95 10 years ago
6 Three-Source Extractors for Polylogarithmic Min-Entropy
Xin Li
🔮 The Ethereal cs.CC 68 11 years ago
7 Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams
🔮 The Ethereal cs.CC 53 7 years ago
8 Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
Michael Kapralov, Jelani Nelson, ... (+4 more)
🔮 The Ethereal cs.CC 48 8 years ago
9 Isomorphism Testing for Graphs of Bounded Rank Width
Martin Grohe, Pascal Schweitzer
🔮 The Ethereal cs.DM 47 10 years ago
10 On the Quantitative Hardness of CVP
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
🔮 The Ethereal cs.CC 42 8 years ago
11 The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
Enric Boix-Adserà, Matthew Brennan, Guy Bresler
🔮 The Ethereal cs.CC 42 7 years ago
12 Algorithms and Barriers in the Symmetric Binary Perceptron Model
David Gamarnik, Eren C. Kızıldağ, ... (+2 more)
🔮 The Ethereal cs.CC 42 4 years ago
13 Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Amir Abboud, Arturs Backurs, ... (+2 more)
🔮 The Ethereal cs.CC 41 8 years ago
14 Uniform generation of random regular graphs
Pu Gao, Nicholas Wormald
🔮 The Ethereal math.CO 40 10 years ago
15 Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, ... (+3 more)
🔮 The Ethereal cs.CC 35 10 years ago
16 Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, ... (+3 more)
🔮 The Ethereal cs.CC 35 8 years ago
17 PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
🔮 The Ethereal cs.CC 35 7 years ago
18 A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, ... (+2 more)
🔮 The Ethereal cs.CC 32 10 years ago
19 Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More
Xin Li
🔮 The Ethereal cs.CC 32 3 years ago
20 Sublinear Algorithms for Gap Edit Distance
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
🔮 The Ethereal cs.CC 31 6 years ago
21 Flip-width: Cops and Robber on dense graphs
Szymon Toruńczyk
🔮 The Ethereal math.CO 31 3 years ago
22 Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald
🔮 The Ethereal math.CO 29 6 years ago
23 New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
🔮 The Ethereal cs.CC 28 5 years ago
24 Learning sums of powers of low-degree polynomials in the non-degenerate case
Ankit Garg, Neeraj Kayal, Chandan Saha
🔮 The Ethereal cs.CC 27 5 years ago
25 Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, Leonid Gurvits, ... (+2 more)
🔮 The Ethereal math.CO 25 8 years ago
26 Junta correlation is testable
Anindya De, Elchanan Mossel, Joe Neeman
🔮 The Ethereal cs.CC 22 6 years ago
27 Hardness Results for Structured Linear Systems
Rasmus Kyng, Peng Zhang
🔮 The Ethereal cs.CC 21 8 years ago
28 Noisy population recovery in polynomial time
Anindya De, Michael Saks, Sijian Tang
🔮 The Ethereal cs.CC 18 10 years ago
29 Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, ... (+3 more)
🔮 The Ethereal cs.CC 17 2 years ago
30 Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
🔮 The Ethereal cs.DM 15 7 years ago
31 Explicit near-fully X-Ramanujan graphs
Ryan O'Donnell, Xinyu Wu
🔮 The Ethereal math.CO 15 5 years ago
32 Certified Hardness vs. Randomness for Log-Space
Edward Pyne, Ran Raz, Wei Zhan
🔮 The Ethereal cs.CC 15 3 years ago
33 Killing a Vortex
Dimitrios M. Thilikos, Sebastian Wiederrecht
🔮 The Ethereal math.CO 13 3 years ago
34 Induced Cycles and Paths Are Harder Than You Think
Mina Dalirrooyfard, Virginia Vassilevska Williams
🔮 The Ethereal cs.CC 13 3 years ago
35 Random $k$-out subgraph leaves only $O(n/k)$ inter-component edges
Jacob Holm, Valerie King, ... (+3 more)
🔮 The Ethereal cs.DM 12 6 years ago
36 Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, ... (+2 more)
🔮 The Ethereal cs.DM 12 2 years ago
37 Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces
Luke Postle
🔮 The Ethereal math.CO 11 6 years ago
38 Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds
Manik Dhar, Zeev Dvir
🔮 The Ethereal math.CO 10 3 years ago
39 Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, ... (+2 more)
🔮 The Ethereal cs.CC 10 3 years ago
40 Improved Extractors for Small-Space Sources
Eshan Chattopadhyay, Jesse Goodman
🔮 The Ethereal cs.CC 9 5 years ago
41 Properly Learning Decision Trees with Queries Is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan
🔮 The Ethereal cs.CC 9 2 years ago
42 Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Dmitriy Kunisky, Xifan Yu
🔮 The Ethereal cs.CC 8 1 year ago
43 Explicit Lossless Vertex Expanders
Jun-Ting Hsieh, Alexander Lubotzky, ... (+3 more)
🔮 The Ethereal math.CO 8 11 months ago
44 A characterization of testable hypergraph properties
Felix Joos, Jaehoon Kim, ... (+2 more)
🔮 The Ethereal math.CO 7 8 years ago
45 Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar
🔮 The Ethereal cs.CC 7 3 years ago
46 Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett, Jiapeng Zhang
🔮 The Ethereal cs.CC 7 3 years ago
47 Traversing combinatorial 0/1-polytopes via optimization
Arturo Merino, Torsten Mütze
🔮 The Ethereal cs.DM 7 2 years ago
48 Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
🔮 The Ethereal cs.CC 7 11 months ago
49 The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio
András Sebő, Anke van Zuylen
🔮 The Ethereal cs.DM 6 9 years ago
50 The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
🔮 The Ethereal cs.CC 6 8 years ago