DERANDOMIZATION, WITNESSES FOR BOOLEAN MATRIX MULTIPLICATION AND CONSTRUCTION OF PERFECT HASH FUNCTIONS

Small sample spaces with almost independent random variables are appli ed to design efficient sequential deterministic algorithms for two pro blems. The first algorithm, motivated by the attempt to design efficie nt algorithms for the All Pairs Shortest Path problem using fast matri x multiplication, solves the problem of computing witnesses for the Bo olean product of two matrices. That is, if A and B are two n by n matr ices, that A(ik) = B-kj = 1. Its running time exceeds that of computin g the product of two n by n matrices with small integer entries by a p olylogarithmic factor The second algorithm is a nearly linear time det erministic procedure for constructing a perfect hash function for a gi ven n-subset of {1,...,m}.