Paper Info
Title
Pseudorandomness for approximate counting and sampling
Abstract
We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions. Our main technical contribution allows one to "boost" a given hardness assumption. One special case is a proof that EXP 驴 NP/poly 驴 EXP 驴 P_\parallel ^{NP}/poly. In words, if there is a problem in EXP that cannot be computed by poly-size nondeterministic circuits then there is one which cannot be computed by poly-size circuits that make non-adaptive NP oracle queries. This in particular shows that the various assumptions used over the last few years by several authors to derandomize Arthur-Merlin games (i.e., show AM = NP) are in fact all equivalent. In addition to simplifying the framework of AM derandomization, we show that this "unified assumption" suffices to derandomize several other probabilistic procedures. For these results we define two new primitives that we regard as the natural pseudorandom objects associated with approximate counting and sampling of NP-witnesses. We use the "boosting" theorem and hashing techniques to construct these primitives using an assumption that is no stronger than that used to derandomize AM. As a consequence, under this assumption, there are deterministic polynomial time algorithms that use non-adaptive NP-queries and perform the following tasks: approximate counting of NP-witnesses: given a Boolean circuit A, output r such that (1 - 驴)|A^-1(1)| 驴 r 驴 |A^-1(1)|. pseudorandom sampling of NP-witnesses: given a Boolean circuit A, produce a polynomial-size sample space that is computationally indistinguishable from the uniform distribution over A^-1(1). We also present applications. For example, we observe that Cai's proof that S_2^P\subseteq ZPP^{NP} and the learning algorithm of Bshouty et al. can be seen as reductions to sampling that are not probabilistic. As a consequence they can be derandomized under the assumption stated above, which is weaker than the assumption that was previously known to suffice.
Year
DOI
Venue
2006
10.1109/CCC.2005.26
Electronic Colloquium on Computational Complexity
Keywords
Field
DocType
boolean circuit,sampling methods,boolean functions,circuit complexity,random number generation,computer science,distributed computing,game theory,computational complexity,learning artificial intelligence,computational modeling,uniform distribution,probability,polynomials
Boolean function,Discrete mathematics,Boolean circuit,Nondeterministic algorithm,Pseudorandomness,Random number generation,Time complexity,Mathematics,Computational complexity theory,Pseudorandom number generator
Journal
Volume
Issue
ISSN
15
4
1420-8954
ISBN
Citations 
PageRank 
0-7695-2364-1
27
0.90
References 
Authors
35
2
Name
Order
Citations
PageRank
Ronen Shaltiel195351.62
Christopher Umans287955.36