The Spatial Complexity of Oblivious k-Probe Hash Functions
From MaRDI portal
Publication:3495640
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
Searching and sorting (68P10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
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
