zbMATH — the first resource for mathematics

Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. (English) Zbl 0857.68055
Summary: 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 computing witnesses for the Boolean product of two matrices. That is, if \(A\) and \(B\) are two \(n\) by \(n\) matrices, and \(C = AB\) is their Boolean product, the algorithm finds for every entry \(C_{ij}=1\) a witness: an index \(k\) so that \(A_{ik} = B_{kj} = 1\). Its running time exceeds that of computing the product of two \(n\) by \(n\) matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfact hash function for a given \(n\)-subset of \(\{1, \dots, m\}\).

68W10 Parallel algorithms in computer science
Full Text: DOI
[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. · Zbl 0631.68063 · doi:10.1016/0196-6774(86)90019-2
[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. · Zbl 0744.94023 · doi:10.1109/18.119713
[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. · Zbl 0877.68090
[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. · Zbl 0977.68562
[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.
[6] N. Alon and J. Spencer,The Probabilistic Method, Wiley, New York, 1991. · Zbl 1333.05001
[7] B. Berger and J. Rompel, Simulating (logc n)-wise independence in NC,Journal of the ACM,38 (1991), 1026–1046. · Zbl 0799.68094 · doi:10.1145/115234.115347
[8] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions,Journal of Symbolic Computation,9 (1990), 251–280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
[9] A. Fiat and M. Naor, ImplicitO(1) probe search,SIAM Journal on Computing,22 (1993), 1–10. · Zbl 0766.68017 · doi:10.1137/0222001
[10] A. Fiat, M. Naor, J. P. Schmidt, and A. Siegel, Non-oblivious hashing,Journal of the ACM,31 (1992), 764–782. · Zbl 0799.68057 · doi:10.1145/146585.146591
[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. · Zbl 0525.68037 · doi:10.1137/0605009
[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. · Zbl 0629.68068 · doi:10.1145/828.1884
[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. · Zbl 0785.65053 · doi:10.1006/jcom.1993.1014
[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. · Zbl 0633.68026 · doi:10.1145/4221.4226
[16] J. Körner, Fredman-Komlós bounds and information theory,SIAM Journal on Algebraic and Discrete Methods,7 (1986), 560–570. · Zbl 0603.05034 · doi:10.1137/0607062
[17] M. Luby, A simple parallel algorithm for the maximal independent set problem,SIAM Journal on Computing,15 (1986), 1036–1053. · Zbl 0619.68058 · doi:10.1137/0215074
[18] M. Luby, Removing randomness in parallel computation without a processor penalty,Journal of Computer Systems and Science,47 (1993), 250–286. · Zbl 0784.68035 · doi:10.1016/0022-0000(93)90033-S
[19] H. Mairson, The effect of table expansion on the program complexity of perfect hash functions,BIT,32 (1992), 430–440. · Zbl 0752.68020 · doi:10.1007/BF02074879
[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. · Zbl 0556.68001
[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. · Zbl 0824.68047
[23] J. Naor and M. Naor, Small-bias probability spaces: efficient constructions and applications,SIAM Journal on Computing,22 (1993), 838–856. · Zbl 0776.60014 · doi:10.1137/0222053
[24] A. Nilli, Perfect hashing and probability,Combinatorics, Probability and Computing,3 (1994), 407–419. · Zbl 0820.68063 · doi:10.1017/S0963548300001280
[25] P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs,Journal of Computer Systems and Science,37 (1988), 130–143. · Zbl 0659.90066 · doi:10.1016/0022-0000(88)90003-7
[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. · Zbl 0711.68039 · doi:10.1137/0219054
[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. · Zbl 0703.05046
[30] R. E. Tarjan and A. C. Yao, Storing a Sparse Table,Communications of the ACM,22 (1979), 606–611. · Zbl 0414.68038 · doi:10.1145/359168.359175
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.