The Spatial Complexity of Oblivious k-Probe Hash Functions

DOI10.1137/0219054zbMath0711.68039OpenAlexW2079301493MaRDI QIDQ3495640

Jeanette P. Schmidt, Alan R. 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 hashingspatial complexitypower bound

Mathematics Subject Classification ID

Related Items (28)

Improved bounds for dictionary look-up with one error ⋮ The parameterized complexity of unique coverage and its variants ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Packing arc-disjoint cycles in tournaments ⋮ Efficient construction of a small hitting set for combinatorial rectangles in high dimension ⋮ Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions ⋮ Parameterized edge Hamiltonicity ⋮ Perfect hashing ⋮ Flash memory efficient LTL model checking ⋮ Variants of constrained longest common subsequence ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Encoding 2D range maximum queries ⋮ Graphs, hypergraphs and hashing ⋮ Parameterized complexity of even/odd subgraph problems ⋮ Confronting intractability via parameters ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Polynomial hash functions are reliable ⋮ An approximation algorithm for computing longest paths. ⋮ The Budgeted Unique Coverage Problem and Color-Coding ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Unnamed Item ⋮ Linear-space data structures for range frequency queries on arrays and trees

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