A Caltech Library Service

Pseudorandomness for Approximate Counting and Sampling

Shaltiel, Ronen and Umans, Christopher (2006) Pseudorandomness for Approximate Counting and Sampling. Computational Complexity, 15 (4). pp. 298-341. ISSN 1016-3328.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study computational procedures that use both randomness and nondeterminism. 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: We show that 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. We also 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. We observe that Cai's proof that S_2^P ⊆ PP⊆(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 an assumption which is weaker than the assumption that was previously known to suffice.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2007 Birkhäuser Verlag. Open Access. Manuscript received 15 September 2005. Some of R. Shaltiel’s work was done while at the Weizmann Institute and supported by the Koshland Scholarship. This research was also supported by BSF grant 2004329. C. Umans’ research was supported by NSF grant CCF-0346991, BSF grant 2004329, and an Alfred P. Sloan Research Fellowship. We thank Lance Fortnow, Oded Goldreich, Russell Impagliazzo, Rahul Santhanam, Amnon Ta-Shma and Salil Vadhan for helpful comments. We also thank the anonymous referees for numerous helpful comments and suggestions.
Funding AgencyGrant Number
Koshland ScholarshipUNSPECIFIED
Alfred P. Sloan Research FellowshipUNSPECIFIED
Subject Keywords:Derandomization; pseudorandomness; Arthur Merlin games; approximate counting; nondeterministic circuits
Classification Code:68Q15
Record Number:CaltechAUTHORS:20110811-085055181
Persistent URL:
Official Citation:Pseudorandomness for Approximate Counting and Sampling Ronen Shaltiel and Christopher Umans pp.298-341
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24797
Deposited By: Ruth Sustaita
Deposited On:11 Aug 2011 16:43
Last Modified:26 Dec 2012 13:28

Repository Staff Only: item control page