| 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 |