Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-026 | 6th September 2014 00:47

Time Hierarchies for Sampling Distributions

RSS-Feed




Revision #2
Authors: Thomas Watson
Accepted on: 6th September 2014 00:47
Downloads: 950
Keywords: 


Abstract:

We show that "a little more time gives a lot more power to sampling algorithms." We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, 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-\epsilon$ 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 $\epsilon>0$, there exists a family of distributions that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-\epsilon$ 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.


Revision #1 to TR12-026 | 25th June 2012 06:22

Time Hierarchies for Sampling Distributions





Revision #1
Authors: Thomas Watson
Accepted on: 25th June 2012 06:22
Downloads: 2624
Keywords: 


Abstract:

We show that "a little more time gives a lot more power to sampling algorithms." We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, 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-\epsilon$ 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 $\epsilon>0$, there exists a family of distributions that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-\epsilon$ 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.


Paper:

TR12-026 | 27th March 2012 02:10

Time Hierarchies for Sampling Distributions





TR12-026
Authors: Thomas Watson
Publication: 27th March 2012 03:31
Downloads: 2762
Keywords: 


Abstract:

We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, 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-\epsilon$ in time $t$. Our proof involves reducing the problem to a communication problem over a certain type of noisy channel. We solve the latter problem by giving a construction of a new 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.



ISSN 1433-8092 | Imprint