Theory of Computing
-------------------
Title : Monotone Circuits: One-Way Functions versus Pseudorandom Generators
Authors : Oded Goldreich and Rani Izsak
Volume : 8
Number : 10
Pages : 231-238
URL : http://www.theoryofcomputing.org/articles/v008a010
Abstract
--------
We study the computability of one-way functions and pseudorandom
generators by monotone circuits, showing a substantial gap between
the two: On one hand, there exist one-way functions that are
computable by (uniform) polynomial-size monotone functions,
provided (of course) that one-way functions exist at all. On the
other hand, no monotone function can be a pseudorandom generator.