On the Yu--Tan Conjecture for Non-Interactive Simulation of Binary Random Variables

Two parties observe the strings $x,y\in\{-1,1\}^n$ of first and second bits of $n$ independent pairs of uniform bits, the bits of each pair agreeing with probability $(1+\rho)/2$. Without communicating, each party outputs 1 exactly when its string lies in a set of measure $1/4$. Yu and Tan conjectured that the smallest probability that both outputs equal 1 is $((1-\rho)/4)^2$, the value that the subcubes $\{x:x_1=x_2=1\}$ and $\{y:y_1=y_2=-1\}$ attain. For large $\rho$, we disprove the conjecture with sets $A,B$ of measure $1/4$ such that every point of $A$ differs from every point of $B$ in at least 3 coordinates, so that the probability vanishes to third order as $\rho\to1$, whereas the conjectured value vanishes to second order. The disproof also refutes a theorem of Salehi and Shirani that implies the conjecture and that fails with three pairs of bits when the outputs equal 1 with probabilities $1/8$ and $1/2$. For small $\rho$, we prove the conjecture by expanding the probability in $\rho$. The first-level Fourier weight of a set of measure $1/4$, the sum of the squared degree-1 Fourier coefficients of its indicator, is at most $1/8$, so the Cauchy--Schwarz inequality bounds the first-order term below by $-\rho/8$. If the weight falls short of $1/8$ by $\delta\le1/1600$, the set differs from a codimension-2 subcube on at most a fraction $36\delta$ of $\{-1,1\}^n$, which bounds the higher-order terms. The conjecture fails at $n=9$ for every $\rho\in(0.6854,1)$ and, as $n$ grows, for every $\rho\in(0.6829,1)$, whereas it holds for every $n$ when $0\le\rho\le 1/401$.