## Derandomization, Witnesses for Boolean
Matrix Multiplication and Construction of Perfect Hash Functions

### Noga Alon and Moni Naor

### Abstract:

In this paper we show how to make two very efficient probabilistic algorithms
deterministic at a relatively small degradation in their performance. Very
small sample spaces with almost independent random variables are applied
together with an efficient search mechanism in order to design efficient
sequential deterministic algorithms as follows:

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*
x *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 *x* 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*. (For this problem the Fredman-Komlos-Szemeredi scheme
yields a probabilistic algorithm.)
Postscript , gzipped Postscript,
PDF .

Back to On-Line Publications

Back Home