Home
Scholarly Works
On derandomization and average-case complexity of...
Journal article

On derandomization and average-case complexity of monotone functions

Abstract

We investigate whether circuit lower bounds for monotone circuits can be used to derandomize randomized monotone circuits. We show that, in fact, any derandomization of randomized monotone computations would derandomize all randomized computations, whether monotone or not. We prove similar results in the settings of pseudorandom generators and average-case hard functions — that a pseudorandom generator secure against monotone circuits is also secure with somewhat weaker parameters against general circuits, and that an average-case hard function for monotone circuits is also hard with somewhat weaker parameters for general circuits.

Authors

Karakostas G; Kinne J; van Melkebeek D

Journal

Theoretical Computer Science, Vol. 434, , pp. 35–44

Publisher

Elsevier

Publication Date

May 25, 2012

DOI

10.1016/j.tcs.2012.02.017

ISSN

0304-3975

Contact the Experts team