## 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 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 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 language | English (US) |
---|---|

Pages (from-to) | 434-449 |

Number of pages | 16 |

Journal | Algorithmica (New York) |

Volume | 16 |

Issue number | 4-5 |

DOIs | |

State | Published - 1996 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Derandomization
- Matrix multiplication
- Perfect hashing