Boris Tsirelson showed that the Grothendieck constants play an essential role in the problem of quantum nonlocality: the Tsirelson bound of any full correlation bipartite Bell inequality for a quantum system of dimension d is upperbounded by . Lower bounds Some historical data on best known lower bounds of is summarized in the following table. Upper bounds Some historical data on best known upper bounds of : Applications Cut norm estimation Given an real matrix , the cut norm of is defined by The notion of cut norm is essential in designing efficient approximation algorithms for dense graphs and matrices. More generally, the definition of cut norm can be generalized for symmetric measurable functions so that the cut norm of is defined by This generalized definition of cut norm is crucial in the study of the space of graphons, and the two definitions of cut norm can be linked via the adjacency matrix of a graph. An application of the Grothendieck inequality is to give an efficient algorithm for approximating the cut norm of a given real matrix ; specifically, given an real matrix, one can find a number such that where is an absolute constant. This approximation algorithm uses semidefinite programming. We give a sketch of this approximation algorithm. Let be matrix defined by One can verify that by observing, if form a maximizer for the cut norm of , then form a maximizer for the cut norm of . Next, one can verify that , where Although not important in this proof, can be interpreted to be the norm of when viewed as a linear operator from to . Now it suffices to design an efficient algorithm for approximating . We consider the following semidefinite program: Then . The Grothedieck inequality implies that . Many algorithms (such as interior-point methods, first-order methods, the bundle method, the augmented Lagrangian method) are known to output the value of a semidefinite program up to an additive error in time that is polynomial in the program description size and . Therefore, one can output which satisfies Szemerédi's regularity lemma Szemerédi's regularity lemma is a useful tool in graph theory, asserting (informally) that any graph can be partitioned into a controlled number of pieces that interact with each other in a pseudorandom way. Another application of the Grothendieck inequality is to produce a partition of the vertex set that satisfies the conclusion of