- Authors: G. Karakostas, J. Kinne, and D. van Melkebeek.
- Reference: Theoretical Computer Science, 434: 35-44, 2012.
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.
