# The Coin Problem for Product Tests

The Coin Problem for Product Tests Let Xm, be the distribution over m bits X1,,Xm where the Xi are independent and each Xi equals 1 with probability (1)/2 and 0 with probability (1 )/2. We consider the smallest value of such that the distributions Xm, and Xm, 0 can be distinguished with constant advantage by a function f : 0,1m S, which is the product of k functions f1,f2,, fk on disjoint inputs of n bits, where each fi : 0,1n 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

# The Coin Problem for Product Tests

, Volume 10 (3): 10 – Jun 8, 2018
10 pages

/lp/association-for-computing-machinery/the-coin-problem-for-product-tests-xtnCE1tJWj
Publisher
Association for Computing Machinery
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3201787
Publisher site
See Article on Publisher Site

### Abstract

Let Xm, be the distribution over m bits X1,,Xm where the Xi are independent and each Xi equals 1 with probability (1)/2 and 0 with probability (1 )/2. We consider the smallest value of such that the distributions Xm, and Xm, 0 can be distinguished with constant advantage by a function f : 0,1m S, which is the product of k functions f1,f2,, fk on disjoint inputs of n bits, where each fi : 0,1n 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.

### Journal

ACM Transactions on Computation Theory (TOCT)Association for Computing Machinery

Published: Jun 8, 2018

Keywords: Coin problem

### References

Access the full text.