廣義雜湊

前導

定理一

給定一有效可逼近的機率分布 $D$ 及其於某個k-限 $f_i$ 上的密度 $\epsilon$，並給出一個instance 以及精度參數$0<\delta <1$ 可以得到一個不大於$\lceil \frac{k\ln m+\ln s}{(1-\delta )\epsilon }\rceil$的解$A$，且時間複雜度是$m,s,k^k,q^k,{\epsilon }^{-1},{\delta }^{-1}$的多項式函數。

(第四章)

與asym. optimal errCrct. code的關係

Alon1992 中指出的

定義

• $\mathrm{\Sigma }$ 是一個具字母數為$q\doteq |\mathrm{\Sigma }|$ 的鍵集。
• 任何子集$C\subset {\mathrm{\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$中每一個${\mathrm{\Sigma }}^n$的元素)，其中第 i 個字母表示作$x_{i\in [n]}^j$
• t-hashing：一個參數$t>2$，當某個編碼 $C$ 的任 $t$ 個元素必存在一個位置 $i\in [n]$ 足以區別該 $t$ 個元素，即是$\mathrm{\forall }u\in [t]j_u\in [M],\mathrm{\exists }i\in [n]\text{ st.}{x}_i^{j_{u1}}\ne x_i^{j_{u2}}$，此時稱該編碼是一個 t-雜湊函數。
• (m,q,k)-perfect hash family是一群雜湊函數H

與 k限之間之關係

(t,k)-hashing是一種k限問題。

雜湊函數$h:[m]\to [q]$可以被視為是一個字串$s\in [q{]}^m$，$h(x\in [m])$對應到$s[x]$。 k個限制$<math>f_{T,i\in [t]}\to \{0,1\},f(x)=1\text{iff}\mathrm{\forall }i\in T\mathrm{\forall }j\ne i\in [u],x[i]\ne x[j]$，此處$s=(\genfrac{}{}{0ex}{}{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:\mathrm{\forall }i,x_i\in P_i(X)\}$