Algorithmic derandomization via complexity theory

ABSTRACT

We point out how the methods of Nisan [31, 32], originally developed for derandomizing space-bounded computations, may be applied to obtain polynomial-time and NC derandomizations of several probabilistic algorithms. Our list includes the randomized rounding steps of linear and semi-definite programming relaxations of optimization problems, parallel derandomization of discrepancy-type problems, and the Johnson--Lindenstrauss lemma, to name a few.A fascinating aspect of this style of derandomization is the fact that we often carry out the derandomizations directly from the statements about the correctness of probabilistic algorithms, rather than carefully mimicking their proofs.

REFERENCES

• 1: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 2: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 3: N. Alon and J. Spencer. The Probabilistic Method. Wiley, 1992. With an appendix by P. Erdós.
• 4: Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258593]
• 5: B. Berger and J. Rompel. Simulating (logcn)-wise independence in NC. In Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, pages 2--7, 1989.
• 6: Benny Chor , Oded Goldreich, RSA/Rabin least significant bits are 1-2- + 1/poly(log N) secure, Proceedings of CRYPTO 84 on Advances in cryptology, p.303-313, August 1985, Santa Barbara, California, United States
• 7: S. Dasgupta and A. Gupta. An elementary proof of the Johnson--Lindenstrauss lemma. Technical Report 99-006, University of California, Berkeley, 1999.
• 8: Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
• 9: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 10: Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
• 11: Michel X. Goemans , David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, v.7 n.4, p.656-666, Nov. 1994 [doi>10.1137/S0895480192243516]
• 12: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 13: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 14: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 15: W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability, pages 189--206. American (MATH)ematical Society, 1984.
• 16: D. Karger and D. Koller. (De)randomized construction of small sample spaces in NC. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 252--263, 1994.
• 17: David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998 [doi>10.1145/274787.274791]
• 18: David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
• 19: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
• 20: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 21: Daphne Koller , Nimrod Megiddo, Constructing small sample spaces satisfying given constraints, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.268-277, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167168]
• 22: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. In Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994. Journal version in Combinatorica, 15(2):215--245, 1995.
• 23: M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
• 24: Sanjeev Mahajan , H. Ramesh, Derandomizing Approximation Algorithms Based on Semidefinite Programming, SIAM Journal on Computing, v.28 n.5, p.1641-1663, April/May 1999 [doi>10.1137/S0097539796309326]
• 25: Sanjeev Mahajan , Edgar A. Ramos , K. V. Subrahmanyam, Solving Some Discrepancy Problems in NC, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.22-36, December 18-20, 1997
• 26: Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Journal of Computer and System Sciences, v.49 n.3, p.478-516, Dec. 1994
• 27: R. Motwani, J. Naor, and P. Raghavan. Randomization in approximation algorithms. In D. Hochbaum, editor, Approximation Algorithms. PWS Publishers, 1995.
• 28: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 29: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 30: J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
• 31: N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
• 32: Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
• 33: N. Nisan, E. Szemerédi, and A. Wigderson. Undirected connectivity in O(log1.5 n) space. In Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 24--29, 1992.
• 34: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 35: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 36: Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
• 37: M. Saks , S. Zhou, RSPACE(S) " DSPACE(S^3/2), Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.344, October 23-25, 1995
• 38: Leonard J. Schulman, Sample spaces uniform on neighborhoods, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.17-25, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129715]
• 39: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• 40: Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
• 41: Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]
• 42: Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195420]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Experimentation, Performance, Theory