9 papers · 1 filter
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…
Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
Rishav Gupta, Bingkai Lin, Xin Zheng
We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (), yields tight lower bounds for approximating the parameterized Maximum…
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant such tha…
Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
Shuangle Li, Bingkai Lin, Yuwei Liu
In this paper we present a new gap-creating randomized self-reduction for parameterized Maximum Likelihood Decoding problem over (-MLD). The reduction takes a…
Parameterized Inapproximability Hypothesis under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the numb…
Constant Approximating k-Clique is W[1]-hard
Bingkai Lin
For every graph , let be the largest size of complete subgraph in . This paper presents a simple algorithm which, on input a graph , a positive integer and a sm…