Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs
Johan Håstad · 2018
This is the Knuth Prize lecture. We discuss the approximability of Boolean Constraint Satisfaction Problems (CSPs). In this situation we are given a large number of constraints, each of the form of a fixed predicate P applied to a sequence of literals. The goal is to find an assignment that satisfies the maximum number of constrains.