Monotone Circuits: One-Way Functions versus Pseudorandom Generators

by Oded Goldreich and Rani Izsak

Theory of Computing, Volume 8(10), pp. 231-238, 2012

Bibliography with links to cited articles

[1]   M. Ajtai, J. Komlós, and E. Szemerédi: An O(nlog n) sorting network. In Proc. 15th STOC, pp. 1–9. ACM Press, 1983. [doi:10.1145/800061.808726]

[2]   Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz: Cryptography in NC0. SIAM J. Comput., 36:845–888, 2006. [doi:10.1137/S0097539705446950]

[3]   S. J. Berkowitz: On some relationships between monotone and non-monotone circuit complexity. Technical report, University of Toronto, 1982.

[4]   Manuel Blum and Silvio Micali: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13:850–864, 1984. Preliminary version in FOCS’82. [doi:10.1137/0213053]

[5]   Oded Goldreich: Foundations of Cryptography: Basic Tools. Volume 1. Cambridge University Press, 2001.

[6]   Oded Goldreich: Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[7]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28:1364–1396, 1999. [doi:10.1137/S0097539793244708]

[8]   Jeff Kahn, Gil Kalai, and Nathan Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21923]

[9]   Noam Nisan and Avi Wigderson: Hardness vs. randomness. J. Comput. System Sci., 49:149–167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1]

[10]   Michel Talagrand: How much are increasing sets positively correlated? Combinatorica, 16:243–258, 1996. [doi:10.1007/BF01844850]

[11]   Andrew C. Yao: Theory and application of trapdoor functions. In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc. Press, 1982. [doi:10.1109/SFCS.1982.95]