Krivine rounding scheme

For a bipartite elliptope matrix $X$, put $t=\log (1+\sqrt{2})$ and apply $\sinh (tx)$ within the two diagonal blocks and $\sin (tx)$ across them. Matching absolute power series coefficients give a positive semidefinite matrix by coefficient-dominated entrywise positivity, while $\sinh t=1$ gives unit diagonal. Gaussian hyperplane rounding then turns each cross-block correlation coefficient into $(2/\pi )\arcsin (\sin (t{X}_{ij}))=(2t/\pi )X_{ij}$ because $t<\pi /2$. The zero diagonal blocks of the bipartite objective eliminate every other contribution.

For bipartite binary quadratic optimization, if $v^{\ast }$ is the sign optimum and $p_{\mathrm{SDP}}^{\ast }$ its semidefinite relaxation of binary quadratic optimization value, then $c_K{p}_{\mathrm{SDP}}^{\ast }\le v^{\ast }\le p_{\mathrm{SDP}}^{\ast }$. The upper bound follows from rank-one lifting. For the lower bound, Krivine rounding scheme preprocessing followed by Gaussian hyperplane rounding has expected objective exactly $c_K{p}_{\mathrm{SDP}}^{\ast }$, and every rounded vector is feasible. Some outcome reaches at least this expectation. No independence of rounded coordinates or positive semidefiniteness of the original bipartite objective is needed.

The Krivine rounding scheme yields $c_K=0.56109985\dots$ as its guaranteed objective factor. It is obtained by normalizing $\sinh t=1$, so $t=\mathrm{arsinh}(1)$ and $c_K=2t/\pi$. This proof gives a valid universal factor for the bipartite sign problem, not a proof that it is optimal.