Journal article
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
Algorithmica, Vol.16(5-Apr), pp.434-449
Oct/1996
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 computing witnesses for the Boolean product of two matrices. That is, if A and B are two n by n matrices, 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 perfect hash function for a given n-subset of {1,...,m}.
Details
- Title
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Creators
- Nirit Alon (null) - The Weizmann Institute of ScienceMoni Naor (null) - 972WIS_INST___83
- Resource Type
- Journal article
- Publication Details
- Algorithmica, Vol.16(5-Apr), pp.434-449; Oct/1996
- Number of pages
- 16
- Language
- English
- DOI
- https://doi.org/10.1007/BF01940874
- Record Identifier
- 993263781003596
Metrics
10 Record Views