bounded independence 1hash function construction 1k-min-wise hashing 1min-wise hashing 1similarity estimation 1sketching 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DS2026
Constructions of -Min-Wise Hash from Bounded Independence
Xue Chen, Shengtang Huang, Xin Li
The paper determines the exact amount of bounded independence required for k‑min‑wise hashing, proving that Θ(k + log 1/δ)-wise independence is both sufficient and necessary, and d…
cs.CR2026
High-Rate Public-Key Pseudorandom Codes for Edit Errors
Shengtang Huang, Xin Li, Songtao Mao +1
Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO '2024), are error-correcting codes whose codewords are computationally indistinguishable from uniformly random stri…
cs.DS2025
Explicit Min-wise Hash Families with Optimal Size
Xue Chen, Shengtang Huang, Xin Li
We study explicit constructions of min-wise hash families and their extension to -min-wise hash families. Informally, a min-wise hash family guarantees that for any fixed subset…