💀 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 Slightly Superexponential Parameterized Problems
Daniel Lokshtanov, Daniel Marx, Saket Saurabh
🔮 The Ethereal cs.CC 147 7 years ago
2 Twin-width II: small classes
Édouard Bonnet, Colin Geniet, ... (+3 more)
🔮 The Ethereal cs.DM 119 5 years ago
3 Multivariate Fine-Grained Complexity of Longest Common Subsequence
Karl Bringmann, Marvin Künnemann
🔮 The Ethereal cs.CC 78 8 years ago
4 Subtree Isomorphism Revisited
Amir Abboud, Arturs Backurs, ... (+3 more)
🔮 The Ethereal cs.CC 52 10 years ago
5 A 1.5-Approximation for Path TSP
Rico Zenklusen
🔮 The Ethereal cs.DM 46 7 years ago
6 An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami
🔮 The Ethereal cs.CC 45 7 years ago
7 Explicit resilient functions matching Ajtai-Linial
Raghu Meka
🔮 The Ethereal cs.CC 44 10 years ago
8 Tight Running Time Lower Bounds for Strong Inapproximability of Maximum $k$-Coverage, Unique Set Cover and Related Problems (via $t$-Wise Agreement Testing Theorem)
Pasin Manurangsi
🔮 The Ethereal cs.CC 44 6 years ago
9 Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
Amit Chakrabarti, Anthony Wirth
🔮 The Ethereal cs.CC 40 10 years ago
10 Discrete Gaussian Sampling Reduces to CVP and SVP
Noah Stephens-Davidowitz
🔮 The Ethereal cs.CC 39 10 years ago
11 Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, ... (+3 more)
🔮 The Ethereal cs.CC 36 7 years ago
12 Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, ... (+6 more)
🔮 The Ethereal math.CO 36 3 years ago
13 Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
T-H. Hubert Chan, Zhiyi Huang, ... (+3 more)
🔮 The Ethereal cs.DM 32 9 years ago
14 Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, ... (+2 more)
🔮 The Ethereal cs.CC 30 6 years ago
15 Non interactive simulation of correlated distributions is decidable
Anindya De, Elchanan Mossel, Joe Neeman
🔮 The Ethereal cs.CC 28 9 years ago
16 On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
🔮 The Ethereal cs.CC 28 5 years ago
17 A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^d$
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri
🔮 The Ethereal cs.DM 26 8 years ago
18 A simple and sharper proof of the hypergraph Moore bound
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty
🔮 The Ethereal math.CO 26 3 years ago
19 Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Ivan Bliznets, Marek Cygan, ... (+3 more)
🔮 The Ethereal cs.CC 25 10 years ago
20 Parallel algorithms and concentration bounds for the Lovasz Local Lemma via witness DAGs
Bernhard Haeupler, David G. Harris
🔮 The Ethereal cs.DM 23 10 years ago
21 Erdős-Pósa property of chordless cycles and its applications
Eun Jung Kim, O-joung Kwon
🔮 The Ethereal math.CO 23 8 years ago
22 Conflict-Free Coloring of Planar Graphs
Zachary Abel, Victor Alvarez, ... (+6 more)
🔮 The Ethereal cs.DM 22 9 years ago
23 Uniform generation of random graphs with power-law degree sequences
Pu Gao, Nicholas Wormald
🔮 The Ethereal math.CO 22 8 years ago
24 The Demand Query Model for Bipartite Matching
Noam Nisan
🔮 The Ethereal cs.CC 19 6 years ago
25 Hardness of Permutation Pattern Matching
Vít Jelínek, Jan Kynčl
🔮 The Ethereal math.CO 18 9 years ago
26 Approximating Multicut and the Demand Graph
Chandra Chekuri, Vivek Madan
🔮 The Ethereal cs.DM 17 9 years ago
27 Resource-Efficient Common Randomness and Secret-Key Schemes
Badih Ghazi, T. S. Jayram
🔮 The Ethereal cs.CC 17 8 years ago
28 Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Marc Roth, Philip Wellnitz
🔮 The Ethereal cs.CC 17 6 years ago
29 The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, ... (+3 more)
🔮 The Ethereal cs.DM 17 6 years ago
30 Deep Weisfeiler Leman
Martin Grohe, Pascal Schweitzer, Daniel Wiebking
🔮 The Ethereal cs.LO 17 6 years ago
31 Dichotomy for Real Holant$^c$ Problems
Jin-Yi Cai, Pinyan Lu, Mingji Xia
🔮 The Ethereal cs.CC 16 9 years ago
32 Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, ... (+2 more)
🔮 The Ethereal cs.CC 16 6 years ago
33 Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions
Xi Chen, Jinyu Xie
🔮 The Ethereal cs.DM 15 10 years ago
34 Doubly Balanced Connected Graph Partitioning
Saleh Soltan, Mihalis Yannakakis, Gil Zussman
🔮 The Ethereal math.CO 15 9 years ago
35 Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
Alfonso Cevallos, Stefan Weltge, Rico Zenklusen
🔮 The Ethereal cs.DM 15 8 years ago
36 Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Eun Jung Kim, Stefan Kratsch, ... (+2 more)
🔮 The Ethereal cs.CC 14 3 years ago
37 Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, ... (+5 more)
🔮 The Ethereal cs.CC 14 3 years ago
38 Strongly refuting all semi-random Boolean CSPs
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
🔮 The Ethereal cs.CC 13 5 years ago
39 Communication Complexity of Permutation-Invariant Functions
Badih Ghazi, Pritish Kamath, Madhu Sudan
🔮 The Ethereal cs.CC 10 10 years ago
40 An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Nikhil Srivastava, Luca Trevisan
🔮 The Ethereal cs.DM 10 8 years ago
41 Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
Kuan Cheng, Xin Li
🔮 The Ethereal cs.CC 10 5 years ago
42 Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova, Alexander Golovnev, ... (+3 more)
🔮 The Ethereal cs.CC 10 3 years ago
43 Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, Li-Yang Tan
🔮 The Ethereal cs.CC 10 3 years ago
44 Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, ... (+3 more)
🔮 The Ethereal math.CO 10 1 year ago
45 Near-optimal approximation algorithm for simultaneous Max-Cut
Amey Bhangale, Subhash Khot, ... (+3 more)
🔮 The Ethereal cs.CC 9 8 years ago
46 On Efficient Distance Approximation for Graph Properties
Nimrod Fiat, Dana Ron
🔮 The Ethereal math.CO 9 6 years ago
47 On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, ... (+2 more)
🔮 The Ethereal cs.CC 9 5 years ago
48 On complex roots of the independence polynomial
Ferenc Bencs, Péter Csikvári, ... (+2 more)
🔮 The Ethereal cs.DM 9 3 years ago
49 Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
Nathaniel Harms, Viktor Zamaraev
🔮 The Ethereal cs.CC 9 2 years ago
50 Counting Small Induced Subgraphs: Hardness via Fourier Analysis
Radu Curticapean, Daniel Neuen
🔮 The Ethereal cs.CC 8 1 year ago