Approximate Homomorphisms of the Algebra of Functions on the Boolean Cube and Sums of Squares Algorithms

Lassere hierarchy is one of the most popular approaches to studying the approximability of combinatorial optimization problems. When applied to problems on the Boolean cube, solutions of Lassere relaxations ——- pseudodistributions ——- acquire special properties, becoming tightly linked to homomorphisms of the algebra of functions. In this work, we explore pseudodistributions on the Boolean cube, for which homomorphism conditions hold partially or/and approximately. Precisely, we describe pseudodistributions with partial homomorphism properties and study the closeness of various approximate homomorphisms to the true homomorphisms on the Boolean cube. In addition, we consider pseudodistributions, for which approximate homomorphism properties hold with some probability, and study their possible applications to rounding the Lassere relaxation of the MAX-CUT problem.