The Coin Problem for Product Tests
Chin Ho Lee, Emanuele Viola · ACM Transactions on Computation Theory · 2018
Let X m,ε be the distribution over m bits X 1 ,…, X m where the X i are independent and each X i equals 1 with probability (1− ε )/2 and 0 with probability (1 − ε )/2. We consider the smallest value ε * of ε such that the distributions X m, ε and X m, 0 can be distinguished with constant advantage by a function f : {0,1} m → S , which is the product of k functions f 1 , f 2 ,…, f k on disjoint inputs of n bits, where each f i : {0,1} n → S and m = nk . We prove that ε * = Θ(1/√ n log k ) if S = [−1,1], while ε * = Θ(1/√ nk ) if S is the set of unit-norm complex numbers.