Pseudorandomness for approximate counting and sampling

Author

Shaltiel, Ronen ; Umans, Christopher

Author_Institution

Dept. of Comput. Sci., Haifa Univ., Israel

fYear

2005

fDate

11-15 June 2005

Firstpage

212

Lastpage

226

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on

ISSN

1093-0159

Print_ISBN

0-7695-2364-1

Type

conf

DOI

10.1109/CCC.2005.26

Filename

1443087