Journal of the ACM Bibliography

Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit OR-dispersers with polylogarithmic degree. Journal of the ACM, 45(1):123-154, January 1998. [BibTeX entry]
Preliminary version

A preliminary version of these results was presented in: Michael Saks, Aravind Srinivasan, and Shiyu Zhou. Explicit dispersers with polylog degree. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 479-488, Las Vegas, Nevada, 29 May-1 June 1995.

Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes -- relations among randomized complexity classes; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms; G.3 [Probability and Statistics] -- probabilistic algorithms

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Derandomization, expander graphs, explicit constructions, hashing lemmas, hardness of approximation, imperfect sources of randomness, measures of information, pseudo-random generators, randomized computation, time-space tradeoffs

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database