Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/iii/paper-339/2/g/solution

The Krivine rounding constant has . Since , the principal real inverse sine satisfies
on every cross-block entry. The matrix has zero diagonal blocks, so those cross blocks are the only contributors to its Frobenius inner product with . Explicitly,
No analogous identity is needed for the diagonal blocks involving .
Combining with the preceding expectation formula and optimality of gives the bipartite sign rounding bound
At least one feasible rounded outcome attains at least this expectation. This is an expectation-based approximation guarantee for the specific bipartite sign problem; no claim is made that is the largest possible constant. The inequalities remain valid when the optimal objective is zero.

New to topics? Read the docs here!