The Coin Problem for Product Tests
The Coin Problem for Product Tests
复制标题
产品测试的硬币问题
DOI：
10.1145/3201787
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Chin Ho Lee;Emanuele Viola
设\(X_{m,\epsilon}\)是\(m\)位\(X_1,\ldots,X_m\)上的分布，其中\(X_i\)是相互独立的，并且每个\(X_i\)取值为\(1\)的概率为\(\frac{1 - \epsilon}{2}\)，取值为\(0\)的概率为\(\frac{1 - \epsilon}{2}\)。我们考虑\(\epsilon\)的最小值\(\epsilon^*\)，使得分布\(X_{m,\epsilon}\)和\(X_{m,0}\)能够被一个函数\(f:\{0,1\}^m\rightarrow S\)以常数优势区分开来，其中\(f\)是\(k\)个函数\(f_1,f_2,\ldots,f_k\)在不相交的\(n\)位输入上的乘积，即每个\(f_i:\{0,1\}^n\rightarrow S\)且\(m = nk\)。我们证明，如果\(S = [-1,1]\)，则\(\epsilon^*=\Theta(\frac{1}{\sqrt{n}\log k})\)；而如果\(S\)是单位范数复数集，则\(\epsilon^*=\Theta(\frac{1}{\sqrt{nk}})\)。
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,1}m → S, which is the product of k functions f1,f2,…, fk on disjoint inputs of n bits, where each fi : {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.