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

N. Alon, M. Naor

Research output: Contribution to journalArticle

83 Scopus citations

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, and C = AB is their Boolean product, the algorithm finds for every entry Cij = 1 a witness: an index k so that Aik = Bkj = 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}.

Original languageEnglish (US)
Pages (from-to)434-449
Number of pages16
JournalAlgorithmica (New York)
Volume16
Issue number4-5
DOIs
StatePublished - 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Derandomization
  • Matrix multiplication
  • Perfect hashing

Fingerprint Dive into the research topics of 'Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions'. Together they form a unique fingerprint.

  • Cite this