Parameterized Complexity Theory

By J. Flum, Martin Grohe. 2006

2,184 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Model Architectures, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Model Architectures

In Algorithms & Complexity

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, background): “This type of lower bound over a subrange of 𝑀 is common in the streaming algorithms literature [92].”
Infeasibility of instance compression and succinct PCPs for NP (2007, neutral): “There are a number of good reference works on parameterized complexity[10, 12, 21].”
Invitation to data reduction and problem kernelization (2007, methodology): “A way to do so has been shaped by Downey and Fellows with the theory of parameterized complexity analysis [16, 18, 30].”
Fast Exact Search in Hamming Space With Multi-Index Hashing (2013, neutral): “To help answer these questions we exploit a well-known bound on the sum of binomial coefﬁcients [9]; i.e., for any 0 < (cid:15) ≤ and η ≥ 1 . where In what follows, n continues to denote the number of q -bit database codes, and r is the Hamming search radius.”
Fast search in Hamming space with multi-index hashing (2012, neutral): “where H( ) ≡ − log2 − (1− ) log2(1− ) is the entropy of a Bernoulli distribution with probability [4].”
Invitation to fixed-parameter algorithms (2007, background): “The earlier monograph of Downey and Fellows [2] and the contemporary one of Flum and Grohe [13] tend to be more extended in material, devoting a good part to the parameterized complexity theory.”
Distributed Compressive CSIT Estimation and Feedback for FDD Multi-User Massive MIMO Systems (2014, methodology): “nd on the CSIT NMAE is given by Corollary 3 (with s c = 0). Therefore, when K !1and s c > 1 2 s, the high SNR NMAE ratio of the proposed scheme vs this baseline is given by O 2s(H( sc s ) 1) ( [41] Lemma 16.19), where H(s c s ) = s log s (1 s )log 1s < , 1 2 < s c s 1. Hence, the NMAE rat”
Lower bounds based on the Exponential Time Hypothesis (2011, methodology): “Parameterization can be employed in many different ways; for general background on the theory, the reader is referred to the monographs [24, 27, 50].”
The Book Review Column (2000, neutral): “A detailed chapter by chapter discussion of contents follows.”
The Discrete Basis Problem (2006, background): “Finally, the problem “Given C and k , is r B ð C Þ (cid:6) k ?” is fixed-parameter tractable , i.e., it can be solved in time polynomial to the size of C , assuming that k is fixed [35], [36].”
(Meta) Kernelization (2009, methodology): “Our results can be seen as what Grohe and Kreutzer call algorithmic meta theorems [36, 44].”
Design and Analysis of Algorithms (2009, methodology): “And in fact, while the problem of optimal browser caching with equal sized files can be computed by a min-cost flow computation [12], we do”
On problems without polynomial kernels (2009, background): “For more background on parameterized complexity, the reader is referred to [7,24,32].”