Lasserre Lower Bounds and Definability of Semidefinite Programming

Anuj Dawar, Pengming Wang

For a large class of optimization problems, namely those that can be expressed as finite-valued constraint satisfaction problems (VCSPs), we establish a dichotomy on the number of…