4 papers
Stronger Lower Bounds for Tree Covers via Cyclic Symmetry
Shengtang Huang
A tree cover of an -point metric space is a collection of dominating trees such that every pairwise distance is approximately preserved by at least one tree. The best known…
Bounded Independence for -Min-Wise Hashing: Tight Bounds and Limitations of Structured Hashing
Xue Chen, Shengtang Huang, Xin Li +1
Min-wise hashing and its -min-wise extension are fundamental tools in sampling, sketching, similarity estimation, etc. A standard approach to constructing such families is bound…
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…
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…