Explicit OR-dispersers with polylogarithmic degree

ABSTRACT

An (N, M, T)-OR-disperser is a bipartite multigraph G=(V, W, E) with |V| = N, and |W| = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants &xgr;, &lgr;, 1 ≥ &xgr; > &lgr; ≥ 0, any sufficiently large N, and for any T ≥ 2(logN) M ≤ 2(log N)&lgr;, we give an explicit elementary construction of an (N, M, T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in N. Using this with known applications of OR-dispersers yields several results. First, our construction implies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed &eegr; > 0, we give the first polynomial-time simulation of RP algorithms using the output of any “&eegr;-minimally random” source. For any integral R > 0, such a source accepts a single request for an R-bit string and generates the string according to a distribution that assigns probability at most 2−R&eegr; to any string. It is minimally random in the sense that any weaker source is insufficient to do a black-box polynomial-time simulation of RP algorithms.

REFERENCES

• 1: Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.177-187, July 07-11, 1997
• 2: Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, A new general derandomization method, Journal of the ACM (JACM), v.45 n.1, p.179-213, Jan. 1998 [doi>10.1145/273865.273933]
• 3: A. E. Andreev , A. E. F. Clementi , J. D. P. Rolim , L. Trevisan, Weak random sources, hitting sets, and BPP simulations, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.264, October 19-22, 1997
• 4: M Blum, Independent unbiased coin flips from a correlated biased source:80a finite state Markov chain, Combinatorica, v.6 n.2, p.97-108, 1986 [doi>10.1007/BF02579167]
• 5: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 6: COHEN, A., AND WIGDERSON, A. 1989. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 14-19.
• 7: FERRENBERG, A. M., LANDAU, D. P., AND WONG, Y.J. 1992. Monte Carlo simulations: Hidden errors form "good" random number generators. Phys. Rev. Lett. 69, 23, 3382-3384.
• 8: Amos Fiat , Moni Naor, Implicit O(1) probe search, SIAM Journal on Computing, v.22 n.1, p.1-10, Feb. 1993 [doi>10.1137/0222001]
• 9: Tsan-Sheng Hsu, Graph augmentation and related problems: theory and practice, University of Texas at Austin, Austin, TX, 1993
• 10: Hsu, T.-S., RAMACHANDRAN, V., AND DEAN, N. 1994. Parallel implementation of algorithms for finding connected components. In Proceedings of DIMACS International Algorithm Implementation Challenge. pp. 1-14.
• 11: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 12: IMPAGLIAZZO, R., AND ZUCKERMAN, D. 1989. How to recycle random bits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 248-253.
• 13: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 14: Noam Nisan, Extracting Randomness: How and Why - A survey, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.44, May 24-27, 1996
• 15: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 16: Miklos Santha, On using deterministic functions to reduce randomness in probabilistic algorithms, Information and Computation, v.74 n.3, p.241-249, Sept. 1987 [doi>10.1016/0890-5401(87)90023-X]
• 17: Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
• 18: Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
• 19: SRINIVASAN, A., AND ZUCKERMAN, D. 1994/1996. Computing with very weak random sources. In Proceedings of the IEEE Symposium of Foundations of Computer Science. IEEE, New York, pp. 264-275. Full version available as Tech. Rep. TRA4/96. Department of Information Systems and Computer Science, National University of Singapore, April 1996.
• 20: Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237877]
• 21: Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986
• 22: Umesh Vazirani, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Combinatorica, v.7 n.4, p.375-392, Dec, 1987 [doi>10.1007/BF02579325]
• 23: Umesh V. Vazirani , Vijay V. Vazirani, Random Polynomial Time is Equal to Semi-Random Polynomial Time, Cornell University, Ithaca, NY, 1988
• 24: VON NEUMANN, J. 1963. Various techniques for use in connection with random digits. In von Neumann's Collected Works. Pergaman, New York, pp. 768-770.
• 25: Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]
• 26: ZUCKERMAN, D. 1990. General weak random source. In Proceedings of the IEEE Symposium of Computer Science. IEEE, New York, pp. 534-543.
• 27: David Zuckerman, Simulating BPP using a general weak random source, Proceedings of the 32nd annual symposium on Foundations of computer science, p.79-89, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185351]
• 28: ZUCKERMAN, D. 1993. NP-complete problems have a version that's hard to approximate. In Proceedings of the IEEE Conference on Structure in Complexity Theory. IEEE, New York, pp. 305-312.
• 29: David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237878]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
derandomization, expander graphs, explicit constructions, hardness of approximation, hashing lemmas, imperfect sources of randomness, measures of information, pseudo-random generators, randomized computation, time-space tradeoffs