On the k-Independence Required by Linear Probing and Minwise Independence

2010/01/01 by Mihai Pǎtraşcu, Mikkel Thorup · 3 citations
Computer Science · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Computer security #Constant (computer programming) #Cryptography and Data Security #Discrete mathematics #Hash function #Independence (probability theory) #Matching (statistics) #Mathematical analysis #Mathematics #Omega #Optimization and Search Problems #Physics #Quantum mechanics #Statistics #Upper and lower bounds

paper · doi:10.1007/978-3-642-14165-2_60

crossref issued 2010/01/01 · crossref published 2010/01/01 · crossref published-print 2010/01/01 · openalex publication_date 2010/01/01 · crossref created 2010/07/05 · crossref deposited 2020/11/24 · crossref indexed 2024/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• Linear Probing with Constant Independence
• New hash functions and their use in authentication and set equality
• Cuckoo hashing

Cited by

• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Even Better Framework for min-wise Based Algorithms
• Linear probing [wikipedia]