Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions | Zendy

Noga Alon | Zendy; Moni Naor | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions

Author(s) -

Noga Alon,

Moni Naor

Publication year - 1996

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/bf01940874

Subject(s) - hash function , mathematics , matrix multiplication , logical matrix , combinatorics , boolean function , discrete mathematics , boolean data type , theory of computation , matrix (chemical analysis) , product (mathematics) , multiplication (music) , perfect hash function , integer (computer science) , algorithm , computer science , cryptography , group (periodic table) , cryptographic hash function , chemistry , physics , materials science , computer security , organic chemistry , geometry , quantum mechanics , programming language , composite material , quantum

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 Csub/subsub/subsub/sub

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research