Combinatorial Gap Theorem and Reductions between Promise CSPs

Libor Barto, Marcin Kozik

A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show…