Russell Impagliazzo
- 1.L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXP- TIME has publishable proofs. Computational Complexity, 3(4):307-318, 1993. Google Scholar
Digital Library
- 2.M. Blum. Independent unbiased coin flips from a correlated biased source: a finite state Markov chain. In 25th Annual Symposium on Foundations of Computer Science, pages 425-433, Singer Island, Florida, 24-26 Oct. 1984. IEEE.Google ScholarDigital Library
- 3.M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850-864, Nov. 1984. Google ScholarDigital Library
- 4.J. Cai, A. Nerurkax, and D. Sivakumax. Hardness and hierarchy theorems for probabilistic quasi-polynomial time. In Proceedings of the Thirty-First Annual A CM Symposium on Theory of Computing, pages 726-735, 1999. Google ScholarDigital Library
- 5.B. Chor and O. Goldreich. On the power of two-point based sampling. Journal of Complexity, 5(1):96-106, Max. 1989. Google ScholarDigital Library
- 6.O. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer-Verlag, Algorithms and Combinatorics, 1998. Google ScholarDigital Library
- 7.R. impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, pages 538-545, Milwaukee, Wisconsin, 23-25 Oct. 1995. IEEE. Google ScholarDigital Library
- 8.R. Impagliazzo, R. Shaltiel, and A. Wigderson. Near optimal conversion of hardness into pseudorandomness. In J Oth Annual Symposium on Foundations of Computer Science. IEEE, 1999. Google ScholarDigital Library
- 9.R. Impagliazzo and A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual A CM Symposium on Theory of Computing, pages 220- 229, E1 Paso, Texas, 4-6 May 1997. Google ScholarDigital Library
- 10.R. Impagliazzo and A. Wigderson. Randomness vs. time: De-randomization under a uniform assumption. In 39th Annual Symposium on Foundations of Computer Science. IEEE, 1998. Google ScholarDigital Library
- 11.A: R. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the Thirty-First Annual A CM Symposium on Theory of Computing, 1999. Google ScholarDigital Library
- 12.N. Nisan. Extracting randomness: How and why: A survey. In Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pages 44-58, Philadelphia, Pennsylvania, 24-27 May 1996. IEEE Computer Society Press. Google ScholarDigital Library
- 13.N. Nisan and A. Ta-Shma. Extracting randomness: A survey and new constructions. In Journal of Computer and System Sciencess, 1998. Google ScholarDigital Library
- 14.N. Nisan and A. Wigderson. Hardness vs. randomness (extended abstract), in ~9th Annual Symposium on Foundations of Computer Science, pages 2-11, White Plains, New York, 24-26 Oct. 1988. iEEE.Google Scholar
- 15.N. Nisan and D. Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43-52, Feb. 1996. Google ScholarDigital Library
- 16.J. Radhakrishnan and A. Ta-Shma. Tight bounds for depth-two superconcentrators. In 38th Annual Symposium on Foundations of Computer Science, pages 585- 594, Miami Beach, Florida, 20-22 Oct. 1997. IEEE. Google ScholarDigital Library
- 17.R. Raz, O. Reingold, and S. Vadhan. Error reduction for extractors, in JOth Annual Symposium on Foundations of Computer Science. IEEE, 1999. Google ScholarDigital Library
- 18.R. Raz, O. Reingold, and S. Vadhan. Extracting all the randomness and reducing the error in trevisan's extractors. In Proceedings of the Thirty-First Annual A CM Symposium on Theory of Computing, 1999. Google ScholarDigital Library
- 19.M. Santha and U. V. Vazirani. Generating quasirandom sequences from slightly-random sources (extended abstract). In ~5th Annual Symposium on Foundations of Computer Science, pages 434-440, Singer Island, Florida, 24-26 Oct. 1984. IEEE.Google Scholar
- 20.M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the xor lemma. In Proceedings of the Thirty-First Annual A CM Symposium on Theory of Computing, 1999. Google ScholarDigital Library
- 21.L. Trevisan. Construction of near-optimal extractors using pseudo-random generators. In Proceedings of the Thirty-First Annual A CM Symposium on Theory of Computing, 1999. Google ScholarDigital Library
- 22.hoih boihoi h oihgoirhht oihoigrhoihi iht0itgh the eigenvalue bound: Explicit construction and applications. In Proceedings of the Twenty-Fifth Annual A CM Symposium on the Theory of Computing, pages 245-251, San Diego, California, 16-18 May 1993. Google ScholarDigital Library
- 23.A. C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 Nov. 1982. IEEE.Google ScholarDigital Library
Index Terms
- Extractors and pseudo-random generators with optimal seed length
Recommendations
Simple extractors via constructions of cryptographic pseudo-random generators
Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) ...
Extractors with weak random seeds
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. Our main results are as follows:
- A long line of research, ...
Bit-Wise Behavior of Random Number Generators
In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Comments