The Spatial Complexity of Oblivious k-Probe Hash Functions

DOI10.1137/0219054MaRDI QIDQ3495640zbMATH OpenOpenAlexFDO

Authors Jeanette P. Schmidt, Alan Siegel

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219054

zbMATH Keywords

hash functionsperfect hashingpower boundspatial complexity

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Nonoblivious hashing
• On the \(k\)-independence required by linear probing and minwise independence
• On the cell probe complexity of membership and perfect hashing
• Two results on tables
• scientific article; zbMATH DE number 1688373

Cited in

(33)

• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Perfect hashing
• An approximation algorithm for computing longest paths.
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Hardness and tractability of the \(\gamma\)-complete subgraph problem
• Parameterized complexity of a coupled-task scheduling problem
• The parameterized complexity of unique coverage and its variants
• Linear-space data structures for range frequency queries on arrays and trees
• Packing arc-disjoint cycles in tournaments
• Improved bounds for dictionary look-up with one error
• The Budgeted Unique Coverage Problem and Color-Coding
• Balanced hashing, color coding and approximate counting
• Implicit O(1) Probe Search
• Variants of constrained longest common subsequence
• Nonoblivious hashing
• Confronting intractability via parameters
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Packing Arc-Disjoint Cycles in Tournaments
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• Polynomial hash functions are reliable (extended abstract)
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• The communication complexity of set intersection and multiple equality testing
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Graphs, hypergraphs and hashing
• Flash memory efficient LTL model checking
• Parameterized complexity of even/odd subgraph problems
• Bounds for \(c\)-ideal hashing
• The limits of local search for weighted k-set packing
• Color coding for the fragment-based docking, design and equilibrium statistics of protein-binding ssRNAs
• Deterministic replacement path covering
• On computing the k-shortcut Fréchet distance
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Algorithm engineering for color-coding with applications to signaling pathway detection

This page was built for publication: The Spatial Complexity of Oblivious k-Probe Hash Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495640)