Baby PIH: Parameterized Inapproximability of Min CSP

Computational Complexity 2026 Open access

Read full text
Authors: Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
DOI: 10.1007/s00037-026-00291-0
Cited by: 0
References: 44

Abstract

Abstract The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $$(1-\varepsilon )$$ ( 1 - ε ) -satisfiable (where the parameter is the number of variables) for some constant $$0

Fields of Study & Subjects

semigroups and automata theory Algorithms and Data Compression Advanced Graph Theory Research

Publication details

Journal / source
Computational Complexity
Publisher
Springer Science and Business Media LLC
Volume
35
Issue
2
Publication date
20 August 2026
Language
EN