Xuandi Ren, University of California, Berkeley

Abstract

The Parameterized Inapproximability Hypothesis (PIH) conjectures that no FPT algorithm can distinguish a satisfiable 2‑variable CSP (2CSP) instance from one in which only a constant fraction of constraints can be satisfied. A minimization analogue introduces r‑list‑satisfiability, where each variable may carry an r‑element list of values and a constraint is deemed satisfied if some choice from the Cartesian product of its two lists meets the allowed pair.

The Baby PIH states that, for every integer r≥1, it is W[1]‑hard to tell a satisfiable 2CSP apart from one that is not even r‑list‑satisfiable. The reduction adapts core combinatorial ideas from the Baby PCP theorem and runs in time polynomial in both variable count and alphabet size, thereby recovering the original Baby PCP as a special case.

Building on this, the Average Baby PIH is shown under the sole assumption W[1]≠FPT. Here, any multi‑assignment that satisfies all constraints must assign on average more than r values per variable, yielding a gap between “exactly one value” versus “average > r values.” A novel FPT self‑reduction amplifies the per‑variable gap of Baby PIH to an average‑value gap.