廣義雜湊

前导

定理一

给定一有效可逼近的机率分布 $D$ 及其于某个k-限 $f_{i}$ 上的密度 $\varepsilon$，并给出一个instance 以及精度参数$0<\delta <1$ 可以得到一个不大于$\lceil {\frac {k\ln m+\ln s}{(1-\delta )\varepsilon }}\rceil$的解$A$，且时间复杂度是$m,s,k^{k},q^{k},\varepsilon ^{-1},\delta ^{-1}$的多项式函数。

(第四章)

与asym. optimal errCrct. code的关系

Alon1992 中指出的

定义

• $\Sigma$ 是一个具字母数为$q\doteq |\Sigma |$ 的键集。
• 任何子集$C\subset \Sigma ^{n},M\doteq |C|$皆被视为(n,M)-code (n 码长、M项的编码)。
• code rate 编码效率定义为 $R=R(C)\doteq \log _{q}{\frac {M}{n}}$
• 一个编码 $C$ 的codeword 字串$x^{j\in [M]}\in C$ ($C$中每一个$\Sigma ^{n}$的元素)，其中第 i 个字母表示作$x_{i\in [n]}^{j}$
• t-hashing：一个参数$t>2$，当某个编码 $C$ 的任 $t$ 个元素必存在一个位置 $i\in [n]$ 足以区别该 $t$ 个元素，即是$\forall u\in [t]j_{u}\in [M],\exists i\in [n]{\text{ st.}}x_{i}^{j_{u1}}\neq x_{i}^{j_{u2}}$，此时称该编码是一个 t-杂凑函数。
• (m,q,k)-perfect hash family是一群杂凑函数H

与 k限之间之关系

(t,k)-hashing是一种k限问题。

杂凑函数$h:[m]\rightarrow [q]$可以被视为是一个字串$s\in [q]^{m}$，$h(x\in [m])$对应到$s[x]$。 k个限制$<math>f_{T,i\in [t]}\rightarrow \{0,1\},f(x)=1{\text{iff}}\forall i\in T\forall j\neq i\in [u],x[i]\neq x[j]$，此处$s={\tbinom {k^{2}}{p}}ut$。

Parent Identifying Code

定义如下：

1. 一个(n,M)-code C的子集 X，给座标$i\in [n]$，有 n 个projection $P_{i}(X)=$就是每个x第 i位置的字元集合。
2. X的envelope $e(X)=\{x\in Q^{n}:\forall i,x_{i}\in P_{i}(X)\}$