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

DOI10.1007/BF01940874zbMath0857.68055OpenAlexW1989682699MaRDI QIDQ1923858

Noga Alon, Moni Naor

Publication date: 3 March 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940874

zbMATH Keywords

matrix multiplicationall pairs shortest path problem

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs, Bounds And Constructions For Threshold Shared Generation Of Authenticators, Quantum and approximation algorithms for maximum witnesses of Boolean matrix products, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Separating Hash Families: A Johnson-type bound and New Constructions, Generalised cumulative arrays in secret sharing, Extreme Witnesses and Their Applications, Parsing by matrix multiplication generalized to Boolean grammars, Linear Time Constructions of Some $$d$$-Restriction Problems, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings, Path Laplacian matrices: introduction and application to the analysis of consensus in networks, Time-Optimal Top-$k$ Document Retrieval, All-pairs bottleneck paths in vertex weighted graphs, A fast output-sensitive algorithm for Boolean matrix multiplication, Are unique subgraphs not easier to find?, All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time, Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs, Some intriguing upper bounds for separating hash families, Improved parallel approximation of a class of integer programming problems, On minimum witnesses for Boolean matrix multiplication, Explicit constructions of perfect hash families from algebraic curves over finite fields, Algebraic methods in the congested clique, Faster multi-witnesses for Boolean matrix multiplication, New space/time tradeoffs for top-\(k\) document retrieval on sequences, Broadcast authentication for group communication, Extreme witnesses and their applications, Optimal linear perfect hash families, Improved algorithms via approximations of probability distributions, Perfect hash families: Probabilistic methods and explicit constructions, Unique subgraphs are not easier to find, A new algorithm for optimal 2-constraint satisfaction and its implications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The effect of table expansion on the program complexity of perfect hash functions
• Witnesses for Boolean matrix multiplication and for transitive closure
• Removing randomness in parallel computation without a processor penalty
• The probabilistic method yields deterministic parallel algorithms
• On the exponent of all pairs shortest path problem
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Storing a sparse table
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Fredman–Komlós bounds and information theory
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Implicit $O(1)$ Probe Search
• Nonoblivious hashing
• Simulating (log ^c n )-wise independence in NC
• Perfect Hashing and Probability