caa a22 4500 467909687 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20061201xx s 000 0 eng 10.1007/s00037-007-0218-9 doi (NATIONALLICENCE)springer-10.1007/s00037-007-0218-9 Pseudorandomness for Approximate Counting and Sampling [Elektronische Daten] [Ronen Shaltiel, Christopher Umans] Abstract.: 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 $$\rm S^{P}_{2} \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 an assumption which is weaker than the assumption that was previously known to suffice. Birkhäuser Verlag, Basel, 2007 Derandomization nationallicence pseudorandomness nationallicence Arthur Merlin games nationallicence approximate counting nationallicence nondeterministic circuits nationallicence 68Q15 nationallicence Shaltiel Ronen Department of Computer Science, University of Haifa, Mount Carmel, 31905, Haifa, Israel aut Umans Christopher Department of Computer Science, California Institute of Technology, 91125, Pasadena, CA, USA aut computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 298-341 1016-3328 15:4<298 2006 15 37 https://doi.org/10.1007/s00037-007-0218-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-007-0218-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Shaltiel Ronen Department of Computer Science, University of Haifa, Mount Carmel, 31905, Haifa, Israel aut NATIONALLICENCE 700 1- Umans Christopher Department of Computer Science, California Institute of Technology, 91125, Pasadena, CA, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 298-341 1016-3328 15:4<298 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer