Title :
Pseudorandomness for approximate counting and sampling
Author :
Shaltiel, Ronen ; Umans, Christopher
Author_Institution :
Dept. of Comput. Sci., Haifa Univ., Israel
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
Keywords :
Boolean functions; circuit complexity; game theory; learning (artificial intelligence); probability; random number generation; sampling methods; AM derandomization; Arthur-Merlin games; Boolean circuit; NP-witnesses; approximate counting; boosting theorem; deterministic polynomial time algorithms; hardness assumption; hashing techniques; learning algorithm; natural pseudorandom objects; nonadaptive NP oracle queries; nonadaptive NP-queries; nondeterminism; polysize nondeterministic circuits; probability; pseudorandom sampling; uniform distribution; Circuit testing; Computational complexity; Computational modeling; Computer science; Distributed computing; Polynomials; Sampling methods; Scholarships;
Conference_Titel :
Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on
Print_ISBN :
0-7695-2364-1
DOI :
10.1109/CCC.2005.26
