# 定義集

#### 符號及名詞解釋

• [x]表示 ${\displaystyle {1,2,3...x}}$
• 支集(英语：Support，記作${\displaystyle Supp(f)}$)表示一個函數的定義域中所有${\displaystyle x}$使得${\displaystyle f(x)\neq 0}$

## 第一章

### 定義一: k-限制問題

k-限制問題由以下兩個敘述定義：

1. 該問題的輸入為
• 一個大小為 ${\displaystyle q}$ 的字符集 ${\displaystyle \Sigma }$
• 一個長度 ${\displaystyle m}$
• ${\displaystyle s}$ 個函數 ${\displaystyle f_{i\in [s]}:\sigma ^{k}->\{0,1\}}$ ，而每個函數不得為全否定函數，意即 ${\displaystyle \forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1}$
2. 該問題的輸出為一個集合 ${\displaystyle A\subseteq \Sigma ^{m}}$，其中 ${\displaystyle A}$ 的成員 ${\displaystyle a}$ 滿足 ${\displaystyle \displaystyle {\forall i_{t}\ni 1\leq i_{1}

## 第二章

### 命題一：併集限度

Moreover, picking slightly more vectors at random from D should yield a solution with high probability. But note that we do not know of an efficient way to verify a given set of vectors really does form a solution, unless k = Θ(1).

## 第三章

### 定義三：${\displaystyle l_{p}}$-笵距離 (p-笵線性距離)

${\displaystyle \lVert D-P\rVert _{p}\doteq (\Sigma _{a\in \Omega }(|D(a)-P(a)|^{p}))^{\frac {1}{p}}}$

${\displaystyle \Omega }$k-限中爲${\displaystyle \Sigma ^{m}}$，在其中有一機率分布${\displaystyle D}$，他的密度是${\displaystyle \varepsilon }$，有一個在${\displaystyle \Sigma ^{k}}$${\displaystyle D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]}$，若以後未特別定義則如此。

### 定義四：k-項,ε-相近

#### 引理一

D,P是${\displaystyle \Sigma ^{m}}$中，${\displaystyle l_{1}}$kε相近的兩個機率分布，根據定義，可得${\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }$

# 定理與其證明

## 第五章：項鍊分割

### 引理六：連續項鍊分割

Every interval t-coloring has a bsplitting of size (b − 1)t. Let us describe the intuition behind the case of t = b = 2, which provides some insight to the role of topology in the proof. Call one of the types red. Instead of observing some coloring of the unit interval, observe the equivalent coloring of the one-dimensional sphere (a necklace closed at its clasp). Consider some half necklace. If the measure of red within this half is exactly 1 2 , this induces a fair partition, and we are done. Otherwise, assume without loss of generality that this measure is larger than 1 2 . When rotating the necklace 180◦ , the measure of red in the observed half is hence smaller than 1 2 . As the change in the measure is continuous, there must be a half in which this measure is exactly 1 2 . In general, the proof uses a generalization of the Borsuk-Ulam theorem.

t pairwise disjoint subsets t個兩兩不相交的子集。

i= 1 2 3 ... m

## 參考文獻

1. Alon, Noga; Moshkovitz, Dana; Safra, Shmuel. Algorithmic construction of sets for k -restrictions. ACM Transactions on Algorithms. 2006-04, 2 (2): 153–177. ISSN 1549-6325. doi:10.1145/1150334.1150336 （英语）.