We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms.Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C. The main novelty is that the discrepancy set depends on C, so the new derandomization method is not uniform (i.e., not oblivious).The algorithm works in time exponential in k(p(n)) where k(*) is the price of the hitting set generator and p(*) is a polynomial function in the size of C. We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.

Andreev, A., Clementi, A., Rolim, J. (1998). A New General Derandomization Method. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 45(1), 179-213 [10.1145/273865.273933].

### A New General Derandomization Method

#### Abstract

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms.Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C. The main novelty is that the discrepancy set depends on C, so the new derandomization method is not uniform (i.e., not oblivious).The algorithm works in time exponential in k(p(n)) where k(*) is the price of the hitting set generator and p(*) is a polynomial function in the size of C. We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.
##### Scheda breve Scheda completa Scheda completa (DC)
1-gen-1998
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
Settore MAT/06 - PROBABILITA' E STATISTICA MATEMATICA
English
Computational Complexity, Probabilistic Algorithms, Pseudo-Random Bit Generators.
Andreev, A., Clementi, A., Rolim, J. (1998). A New General Derandomization Method. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 45(1), 179-213 [10.1145/273865.273933].
Andreev, A; Clementi, A; Rolim, J
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2108/18903`
• ND
• 38
• 26