廣義雜湊

前導

定理一

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

(第四章)

與asym. optimal errCrct. code的關係

Alon1992 中指出的

定義

$Σ$ 是一個具字母數為 $q ≐ | Σ |$ 的鍵集。
任何子集 $C \subset Σ^{n}, M ≐ | C |$ 皆被視為(n,M)-code (n 碼長、M項的編碼)。
code rate 編碼效率定義為 $R = R (C) ≐ \log_{q} \frac{M}{n}$
一個編碼 $C$ 的codeword 字串 $x^{j \in [M]} \in C$ ( $C$ 中每一個 $Σ^{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] st. x_{i}^{j_{u 1}} \neq x_{i}^{j_{u 2}}$ ，此時稱該編碼是一個 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個限制 $< m a t h > f_{T, i \in [t]} \to {0, 1}, f (x) = 1 iff \forall i \in T \forall j \neq i \in [u], x [i] \neq x [j]$ ，此處 $s = (\binom{k^{2}}{p}) u t$ 。

Parent Identifying Code

定義如下：

一個(n,M)-code C的子集 X，給座標 $i \in [n]$ ，有 n 個projection $P_{i} (X) =$ 就是每個x第 i位置的字元集合。

X的envelope $e (X) = {x \in Q^{n} : \forall i, x_{i} \in P_{i} (X)}$