The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes

Abstract

In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORRn (n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORRn grows exponentially in n.The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP.In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORRn</sub. Such spectrahedra are called psd lifts of CORRn. By the way, their work showed the first-known super-polynomial lower bounds on the size of psd lifts of any explicit family of polytopes.An elaboration of this work of [LRS] is the main part of our thesis. It is our objective and intention to present a very detailed version of their proof and in the ideal case a version that makes it easier to understand their brilliant work. In this connection, it is our motivation to bring their work to a broader number of people.On the other hand, we present some of our own ideas by which we even obtain some slightly stronger results than [LRS] at some points. By the way, we illustrate way [LRS] could even show a stronger lower bound than they claimed in their original work.On the whole, this thesis can be divided into three parts. The already mentioned proof of the work of [LRS] forms the second one. In the first part, we present a new and easier proof of a famous and often cited theorem of Grigoriev, where he proved lower bounds on the degree of the Real Nullstellensatz. On the one hand, Grigoriev's Theorem is on its own of high significance for questions concerning the power and complexity of algorithms relying on sums of squares and solving problems as they appear frequently in combinatorial optimization, on the other hand, this results is also essential for the work of [LRS]. We also present two applications of Grigoriev`s theorem respectively its proof.In the last part of our thesis, we take a look on so-called pseudo-expectations and pseudo-densities, Boolean functions with specific properties, that are one of the main ingredients in the proof of [LRS]. We give a detailed analysis on those pseudo-densities that occurs in this proof and we characterizes them in the symmetric case. With this characterizations, we are able to state some optimality results for the lower bounds on the size of psd lifts of the correlation polytopes obtained by [LRS].