Szemerédi's regularity lemma, via the cut norm estimation algorithm, in time that is polynomial in the upper bound of Szemerédi's regular partition size but independent of the number of vertices in the graph. It turns out that the main "bottleneck" of constructing a Szemeredi's regular partition in polynomial time is to determine in polynomial time whether or not a given pair is close to being -regular, meaning that for all with , we have where for all and are the vertex and edge sets of the graph, respectively. To that end, we construct an matrix , where , defined by Then for all , Hence, if is not -regular, then . It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time such that Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al. Variants of the Grothendieck inequality Grothendieck inequality of a graph The Grothendieck inequality of a graph states that for each and for each graph without self loops, there exists a universal constant such that every matrix satisfies that The Grothendieck constant of a graph , denoted , is defined to be the smallest constant that satisfies the above property. The Grothendieck inequality of a graph is an extension of the Grothendieck inequality because the former inequality is the special case of the latter inequality when is a bipartite graph with two copies of as its bipartition classes. Thus, For , the -vertex complete graph, the Grothendieck inequality of becomes It turns out that . On one hand, we have . Indeed, the following inequality is true for any matrix , which implies that by the Cauchy-Schwarz inequality: On the other hand, the matching lower bound is due to Alon, Makarychev, Makarychev and Naor in 2006. The Grothendieck inequality of a graph depends upon the structure of . It is known that and where is the clique number of , i.e., the largest such that there exists with such that for all distinct , and The parameter is known as the Lovász theta function of the complement of . L^p Grothendieck inequality In the application of the Grothendieck inequality for approximating the cut norm, we have seen that the Grothendieck inequality answers the following question: How well does an optimal solution to the semidefinite program approximate , which can be