3 papers
cs.CC2026
Near-Logarithmic Inapproximability of Parameterized Set Cover
Bingkai Lin, Xin Zheng
We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size . Let be the universe size, the number of available sets, and $|Γ|…
cs.CC2026
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…
cs.CC2026
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…