前导

编辑

定理一

编辑

给定一有效可逼近的机率分布   及其于某个k-限   上的密度  ,并给出一个instance 以及精度参数  可以得到一个不大于 的解 ,且时间复杂度是 的多项式函数。

(第四章)

与asym. optimal errCrct. code的关系

编辑

Alon1992 中指出的

定义

编辑
  •   是一个具字母数为  的键集。
  • 任何子集 皆被视为(n,M)-code (n 码长、M项的编码)。
  • code rate 编码效率定义为  
  • 一个编码  codeword 字串  ( 中每一个 的元素),其中第 i 个字母表示作 
  • t-hashing:一个参数 ,当某个编码   的任   个元素必存在一个位置   足以区别该   个元素,即是 ,此时称该编码是一个 t-杂凑函数。
  • (m,q,k)-perfect hash family是一群杂凑函数H

与 k限之间之关系

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

杂凑函数 可以被视为是一个字串  对应到 。 k个限制 ,此处 

Parent Identifying Code

编辑

定义如下:

  1. 一个(n,M)-code C的子集 X,给座标 ,有 n 个projection  就是每个x第 i位置的字元集合。
  2. X的envelope