We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P ( x y ) and Q ( u v ) : The goal is to determine if two players, Alice and Bob, that observe sequences X n and Y n respectively where ( X i Y i ) n i =1 are drawn i.i.d. from P ( x y ) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q ( u v ) . Even when P and Q are extremely simple: e.g., P is uniform on the triples (0 0 ) ( 0 1 ) ( 1 0 ) and Q is a "doubly symmetric binary source", i.e., U and V are uniform 1 variables with correlation say 0 49 , it is open if P can simulate Q .

In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 2 distribution, then the non-interactive simulation problem is decidable: specifically, given 0"> 0 the algorithm runs in time bounded by some function of P and and either gives a non-interactive simulation protocol that is -close to Q or asserts that no protocol gets O ( ) -close to Q . The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P ( x y ) to get -close to Q . We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.