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]