Time hierarchies for sampling distributions
Time hierarchies for sampling distributions
复制标题
抽样分布的时间层次结构
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
T. Watson
中科院分区：
文献类型：
--
作者：
T. Watson
我们证明“多一点时间可以为采样算法提供更多的能力”。我们证明，对于每个常数 k ≥ 2、每个多项式时间界限 t 和每个多项式小 ε，存在 k 个元素的分布族，可以在多项式时间内精确采样，但不能在时间 t 的统计距离 1-1/k-ε 内采样。这意味着在任意大小的域（例如 {0,1}n）上采样分布的一般时间层次结构：对于每个多项式时间界限 t 和每个常数 ε>0，存在一系列分布，可以在多项式时间内精确采样，但不能在时间 t 的统计距离 1-ε 内采样。我们的证明涉及将问题简化为某种类型的噪声信道上的通信问题。为了解决后一个问题，我们使用一种列表可解码代码进行设置，其中错误数量没有限制，但每个错误提供的信息比擦除更多。这种类型的代码可以使用某些已知的传统列表可解码代码来构造，但是我们给出了一种基本的、独立的并且针对这种设置量身定制的新构造。
We show that "a little more time gives a lot more power to sampling algorithms." We prove that for every constant k ≥ 2, every polynomial time bound t, and every polynomially small ε, there exists a family of distributions on k elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance 1-1/k-ε in time t. This implies the following general time hierarchy for sampling distributions on arbitrary-size domains such as {0,1}n: For every polynomial time bound t and every constant ε>0, there exists a family of distributions that can be sampled exactly in polynomial time but cannot be sampled within statistical distance 1-ε in time t. Our proof involves reducing the problem to a communication problem over a certain type of noisy channel. To solve the latter problem we use a type of list-decodable code for a setting where there is no bound on the number of errors but each error gives more information than an erasure. This type of code can be constructed using certain known traditional list-decodable codes, but we give a new construction that is elementary, self-contained, and tailored to this setting.