Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-121 | 12th September 2011 21:44

Monotone Circuits: One-Way Functions versus Pseudorandom Generators

RSS-Feed




TR11-121
Authors: Oded Goldreich, Rani Izsak
Publication: 12th September 2011 21:45
Downloads: 1681
Keywords: 


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.



ISSN 1433-8092 | Imprint