On sketching approximations for symmetric Boolean CSPs

Joanna Boyland, Michael Hwang, Tarun Prasad +2

A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1{\}}^k\to \{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list o…