Skip to main content
SpringerLink
Log in

Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to design efficient algorithms for the All Pairs Shortest Path problem using fast matrix multiplication, solves the problem of computingwitnesses for the Boolean product of two matrices. That is, ifA andB are twon byn matrices, andC=AB is their Boolean product, the algorithm finds for every entryC ij =1 a witness: an indexk so thatA ik =B kj =1. Its running time exceeds that of computing the product of twon byn matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfect hash function for a givenn-subset of {1,...,m}.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

References

  1. N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem,Journal of Algorithms,7 (1986), 567–583.

    Google Scholar 

  2. N. Alon, J. Brusck, J. Naor, M. Naor, and R. Roth, Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs,IEEE Transactions on Information Theory,38 (1992), 509–516.

    Google Scholar 

  3. N. Alon, Z. Galil, and O. Margalit, On the exponent of the All Pairs Shortest Path problem,Proc. 32nd IEEE Annual Symposium on Foundations of Computer Science, 1991, pp. 569–575. AlsoJournal of Computer and System Sciences, to appear.

  4. N. Alon, Z. Galil, O. Margalit. and M. Naor, Witnesses for Boolean matrix multiplication and for shortest paths,Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science, 1992, pp. 417–426.

  5. N. Alon, O. Goldreich, J. Hastad, and R. Peralta, Simple constructions of almostk-wise independent random variables,Proc. 31st IEEE Symposium on Foundations of Computer Science, 1990, pp. 544–553. AlsoRandom Structures and Algorithms,3 (1992), 289–304.

    Google Scholar 

  6. N. Alon and J. Spencer,The Probabilistic Method, Wiley, New York, 1991.

    Google Scholar 

  7. B. Berger and J. Rompel, Simulating (logc n)-wise independence in NC,Journal of the ACM,38 (1991), 1026–1046.

    Google Scholar 

  8. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions,Journal of Symbolic Computation,9 (1990), 251–280.

    Google Scholar 

  9. A. Fiat and M. Naor, ImplicitO(1) probe search,SIAM Journal on Computing,22 (1993), 1–10.

    Google Scholar 

  10. A. Fiat, M. Naor, J. P. Schmidt, and A. Siegel, Non-oblivious hashing,Journal of the ACM,31 (1992), 764–782.

    Google Scholar 

  11. M. L. Fredman and J. Komlós, On the size of separating systems and families of perfect hash functions.SIAM Journal on Algebraic and Discrete Methods,5 (1) (1984), 61–68.

    Google Scholar 

  12. M. L. Fredman, J. Komlós, and E. Szemerédi, Storing a sparse table withO(1) worst case access time,Journal of the ACM,31 (1984), 538–544.

    Google Scholar 

  13. Z. Galil and O. Margalit, A faster algorithm for the all pairs shortest path problem for undirected graphs, Manuscript, August 1991.

  14. Z. Galil and O. Margalit, Witnesses for Boolean matrix multiplication and for transitive closure,Journal of Complexity,9 (1993), 201–221.

    Google Scholar 

  15. R. M. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem,Journal of the ACM,32 (1985), 762–773.

    Google Scholar 

  16. J. Körner, Fredman-Komlós bounds and information theory,SIAM Journal on Algebraic and Discrete Methods,7 (1986), 560–570.

    Google Scholar 

  17. M. Luby, A simple parallel algorithm for the maximal independent set problem,SIAM Journal on Computing,15 (1986), 1036–1053.

    Google Scholar 

  18. M. Luby, Removing randomness in parallel computation without a processor penalty,Journal of Computer Systems and Science,47 (1993), 250–286.

    Google Scholar 

  19. H. Mairson, The effect of table expansion on the program complexity of perfect hash functions,BIT,32 (1992), 430–440.

    Google Scholar 

  20. O. Margalit, Ph.D. Dissertation, Tel Aviv University, 1993.

  21. K. Mehlhorn,Data Structure and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin, 1984.

    Google Scholar 

  22. R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms,Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 8–13.

  23. J. Naor and M. Naor, Small-bias probability spaces: efficient constructions and applications,SIAM Journal on Computing,22 (1993), 838–856.

    Google Scholar 

  24. A. Nilli, Perfect hashing and probability,Combinatorics, Probability and Computing,3 (1994), 407–419.

    Google Scholar 

  25. P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs,Journal of Computer Systems and Science,37 (1988), 130–143.

    Google Scholar 

  26. T. J. Sager, A polynomial time generator for minimal perfect hash functions,Communications of the ACM,28 (1985).

  27. J. Schmidt and A. Siegel, The spatial complexity of obliviousk-probe hash functions,SIAM Journal on Computing,19 (1990), 775–786.

    Google Scholar 

  28. R. Seidel, On the all-pairs-shortest-path problem,Proc. 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 745–749.

  29. J. Spencer,Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, PA, 1987.

    Google Scholar 

  30. R. E. Tarjan and A. C. Yao, Storing a Sparse Table,Communications of the ACM,22 (1979), 606–611.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel

    N. Alon (Incumbent of the Florence and Ted Baumritter Combinatorics and Computer Science Chair)

  2. Department of Applied Mathematics and Computer Science, Weizmann Institute, 76100, Rehovot, Israel

    M. Naor (Incumbent of the Morris and Rose Goldman Career Development Chair)

Authors
  1. N. Alon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Naor
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by M. Luby.

Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.

Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences. Some of this work was done while the author was with the IBM Almaden Research Center.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alon, N., Naor, M. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434–449 (1996). https://doi.org/10.1007/BF01940874

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01940874

Key words

Search

Navigation