2 papers
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…