Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HASH FAMILY:
Reports tagged with hash family:
TR18-096 | 13th May 2018
Venkatesan Guruswami, Andrii Riazanov

#### Beating Fredman-Komlós for perfect $k$-hashing

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>

TR18-116 | 18th June 2018
Xue Chen, David Zuckerman

Revisions: 1

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>> TR19-108 | 23rd August 2019 Chaoping Xing, chen yuan #### Beating the probabilistic lower bound on perfect hashing Revisions: 2 For an interger$q\ge 2$, a perfect$q$-hash code$C$is a block code over$\ZZ_q:=\ZZ/ q\ZZ$of length$n$in which every subset$\{\bc_1,\bc_2,\dots,\bc_q\}$of$q$elements is separated, i.e., there exists$i\in[n]$such that$\{\proj_i(\bc_1),\proj_i(\bc_2),\dots,\proj_i(\bc_q)\}=\ZZ_q$, where$\proj_i(\bc_j)$denotes the$i$th position of$\bc_j$. Finding the maximum size$M(n,q)\$ ... more >>>

ISSN 1433-8092 | Imprint