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