Promise Valued CSPs: an algebraic framework for approximation problems
Silvia Butti ( University of Oxford )
- 14:00 30th November 2023 ( week 8, Michaelmas Term 2023 )Room 051
The Promise Valued Constraint Satisfaction Problem (PVCSP) extends the CSP framework in two independent directions. In the promise setting, each constraint comes in a strong version and a weak version, and the task is to distinguish whether the input is satisfiable in the strong sense, or it is not satisfiable even in the weak sense. In the valued setting, each constraint comes with a payoff, and the goal is to decide whether there exists an assignment whose total payoff is greater than a given threshold. PVCSPs combine and generalize both Promise and Valued CSPs and are general enough to include all constant-factor approximation problems for Max-CSP, such as approximate satisfiability of Boolean CNF-formulas.
In this talk I will discuss a recently developed algebraic framework for obtaining complexity reductions between PVCSPs, heavily inspired by the highly successful algebraic approach to Promise CSPs. I will then show how some well-known inapproximability results can be explained in a new light using this framework.
Joint work with Libor Barto, Alexandr Kazda, Caterina Viola, and Standa Živný.
Share this:
