[x]表示
1
,
2
,
3...
x
{\displaystyle {1,2,3...x}}
支集 (英語：Support ，記作
S
u
p
p
(
f
)
{\displaystyle Supp(f)}
x
{\displaystyle x}
f
(
x
)
≠
0
{\displaystyle f(x)\neq 0}
在有向圖
G
(
V
,
E
)
{\displaystyle G(V,E)}
k-限制問題 由以下兩個敘述定義：
該問題的輸入為
一個大小為
q
{\displaystyle q}
Σ
{\displaystyle \Sigma }
一個長度
m
{\displaystyle m}
s
{\displaystyle s}
f
i
∈
[
s
]
:
σ
k
−
>
{
0
,
1
}
{\displaystyle f_{i\in [s]}:\sigma ^{k}->\{0,1\}}
∀
t
∈
[
s
]
,
∃
x
∈
Σ
k
∋
f
t
(
a
)
=
1
{\displaystyle \forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1}
該問題的輸出為一個集合
A
⊆
Σ
m
{\displaystyle A\subseteq \Sigma ^{m}}
A
{\displaystyle A}
a
{\displaystyle a}
∀
i
t
∋
1
≤
i
1
<
i
2
<
…
<
i
k
≤
m
∀
j
∈
[
s
]
,
∃
a
∈
A
f
j
(
{
a
i
t
}
t
=
1
k
)
=
1
{\displaystyle \displaystyle {\forall i_{t}\ni 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq m\ \forall j\in [s],\exists a\in A\quad f_{j}(\{a_{i_{t}}\}_{t=1}^{k})=1}}
由此可知，
Σ
m
{\displaystyle \Sigma ^{m}}
宇集 )任何必將是任意k-限問題的一個解。但該解為最大解，即任何問題的窮舉 。最理想是剔除掉所有不為解的
a
{\displaystyle a}
NP ，無法於多項式時間內得到該解集合，因此該論文以機率方法 將
A
{\displaystyle A}
A
{\displaystyle A}
a
{\displaystyle a}
給定任意一個機率分佈
D
:
Σ
m
→
[
0
,
1
]
{\displaystyle D:\Sigma ^{m}\rightarrow [0,1]}
D
{\displaystyle D}
a
{\displaystyle a}
D
{\displaystyle D}
a
{\displaystyle a}
ε
{\displaystyle \varepsilon }
ε
≐
min
j
∈
[
s
]
i
1
<
i
2
<
⋯
<
i
k
∈
[
m
]
{
Pr
[
a
∼
D
f
j
(
a
i
1
a
i
2
…
a
i
k
)
=
1
]
}
{\displaystyle \displaystyle {\varepsilon \doteq {\underset {\overset {i_{1}<i_{2}<\dots <i_{k}\in [m]}{j\in [s]}}{\min }}\left\{{\underset {a\sim D}{\Pr[}}\ f_{j}(a_{i_{1}}a_{i_{2}}\dots a_{i_{k}})=1]\right\}}}
可見，每個和k-限問題相關的機率分佈密度皆大於均勻分佈的密度
1
q
m
⋅
q
k
q
m
=
q
−
k
{\displaystyle {\frac {1}{q^{m}}}\cdot {\frac {q^{k}}{q^{m}}}=q^{-k}}
ε
{\displaystyle \varepsilon }
A
{\displaystyle A}
對於每個k-限 及於其上的密度為
ε
{\displaystyle \varepsilon }
D
{\displaystyle D}
⌈
k
ln
m
+
ln
s
ε
⌉
{\displaystyle {\biggr \lceil }{\frac {k\ln m+\ln s}{\varepsilon }}{\biggr \rceil }}
其證明利用反證法 ：
設一個自然數
t
>
k
ln
m
+
ln
s
ε
{\displaystyle t>{\frac {k\ln m+\ln s}{\varepsilon }}}
A
=
{
a
1
,
a
2
,
…
,
a
t
}
⊆
Σ
m
{\displaystyle A=\{a_{1},a_{2},\dots ,a_{t}\}\subseteq \Sigma ^{m}}
a
1
,
…
,
a
t
{\displaystyle a_{1},\dots ,a_{t}}
D
{\displaystyle D}
1
−
x
≤
e
−
x
{\displaystyle 1-x\leq e^{-x}}
Pr
a
1
,
…
,
a
t
∼
D
[
∃
i
[
k
]
∃
j
∀
a
∈
A
,
f
j
(
a
i
1
…
a
i
k
)
=
0
]
≤
(
m
k
)
⋅
s
(
1
−
ε
)
t
≤
exp
(
k
ln
m
+
ln
s
−
ε
t
)
{\displaystyle {\underset {a_{1},\dots ,a_{t}\sim D}{\Pr }}[\exists i_{[k]}\exists j\forall a\in A,f_{j}(a_{i_{1}}\dots a_{i_{k}})=0]\leq {\binom {m}{k}}\cdot s(1-\varepsilon )^{t}\leq \exp(k\ln m+\ln s-\varepsilon t)}
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).
l
p
{\displaystyle l_{p}}
編輯
直接建構出
D
{\displaystyle D}
在取樣空間
Ω
{\displaystyle \Omega }
D
,
P
{\displaystyle D,P}
l
p
{\displaystyle l_{p}}
‖
D
−
P
‖
p
{\displaystyle \lVert D-P\rVert _{p}}
‖
D
−
P
‖
p
≐
(
Σ
a
∈
Ω
(
|
D
(
a
)
−
P
(
a
)
|
p
)
)
1
p
{\displaystyle \lVert D-P\rVert _{p}\doteq (\Sigma _{a\in \Omega }(|D(a)-P(a)|^{p}))^{\frac {1}{p}}}
Ω
{\displaystyle \Omega }
k-限 中爲
Σ
m
{\displaystyle \Sigma ^{m}}
D
{\displaystyle D}
ε
{\displaystyle \varepsilon }
Σ
k
{\displaystyle \Sigma ^{k}}
D
(
i
[
k
]
)
(
a
)
≐
Pr
X
∼
D
[
∀
t
∈
[
k
]
,
a
(
t
)
=
X
(
i
t
)
]
{\displaystyle D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]}
在取樣空間
Σ
m
{\displaystyle \Sigma ^{m}}
D
,
P
{\displaystyle D,P}
∀
0
≤
k
≤
m
∀
i
[
k
]
∈
[
m
]
,
|
|
D
i
[
k
]
−
P
i
[
k
]
|
|
p
<
ε
{\textstyle \forall 0\leq k\leq m\ \forall i_{[k]}\in [m],||D_{i_{[k]}}-P_{i_{[k]}}||p<\varepsilon }
在p-笵上的k-項是ε相近 英語：k-wise ε-close in
l
p
{\displaystyle l_{p}}
。
另外，一個分佈當
∀
p
∀
ε
{\displaystyle \forall p\forall \varepsilon }
U
{\displaystyle U}
k-項獨立 。
D,P是
Σ
m
{\displaystyle \Sigma ^{m}}
l
1
{\displaystyle l_{1}}
|
Pr
X
∼
D
[
f
(
X
(
i
[
k
]
)
=
1
]
−
Pr
X
∼
P
[
f
(
X
(
i
[
k
]
)
=
1
]
|
<
ε
{\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }
展開拆開就結束啦
證明見第五章。
本部分對應到原文的第五至第八章，將以其應用問題解決之。
在此，我們會將k-限 分作數個小部分並分別解決之。根據定理二可以找得到
k
≤
ω
(
log
m
log
log
m
)
{\displaystyle k\leq \omega ({\frac {\log m}{\log \log m}})}
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個兩兩不相交的子集。
傳統上的完全雜湊 (m,q,k)-Perfect Hashing 指的是將
m
{\displaystyle m}
q
{\displaystyle q}
[
m
]
{\displaystyle [m]}
這種雜湊其中的一個推廣是廣義雜湊 (t,u)-Hash Families 在#Alon2003 中出現。
![{\displaystyle f_{i\in [s]}:\sigma ^{k}->\{0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3eb89e6c42a5e94957d845c7cc6740654e36f267)
![{\displaystyle \forall t\in [s],\exists x\in \Sigma ^{k}\ni f_{t}(a)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea50cf95baf712f4f791c5d320310aa63e28416f)
![{\displaystyle \displaystyle {\forall i_{t}\ni 1\leq i_{1}<i_{2}<\ldots <i_{k}\leq m\ \forall j\in [s],\exists a\in A\quad f_{j}(\{a_{i_{t}}\}_{t=1}^{k})=1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dd24265c9b6d11ad605336c61bb3416248f5a01)
![{\displaystyle D:\Sigma ^{m}\rightarrow [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252a5df6b0572a7e10f3cde99debe8ad38831631)
![{\displaystyle \displaystyle {\varepsilon \doteq {\underset {\overset {i_{1}<i_{2}<\dots <i_{k}\in [m]}{j\in [s]}}{\min }}\left\{{\underset {a\sim D}{\Pr[}}\ f_{j}(a_{i_{1}}a_{i_{2}}\dots a_{i_{k}})=1]\right\}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba3396e322fab5c3ea60d8d732b84df18fb026c)
![{\displaystyle {\underset {a_{1},\dots ,a_{t}\sim D}{\Pr }}[\exists i_{[k]}\exists j\forall a\in A,f_{j}(a_{i_{1}}\dots a_{i_{k}})=0]\leq {\binom {m}{k}}\cdot s(1-\varepsilon )^{t}\leq \exp(k\ln m+\ln s-\varepsilon t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6215518b0c06ff54480e6981708816245b1757e4)
![{\displaystyle D_{(i_{[k]})}(a)\doteq \Pr _{X\sim D}[\forall t\in [k],a(t)=X(i_{t})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/334cf90690246bbf6f46756216f627cd88c26f36)
![{\textstyle \forall 0\leq k\leq m\ \forall i_{[k]}\in [m],||D_{i_{[k]}}-P_{i_{[k]}}||p<\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/197005fa3d9045e40818c7b8741bb8fe0c975a58)
![{\textstyle {\biggr |}{\underset {X\sim D}{\Pr }}[f(X(i_{[k]})=1]-{\underset {X\sim P}{\Pr }}[f(X(i_{[k]})=1]{\biggr |}<\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3218e152421fec21fe9be0cefcdbbb2479c131f5)
![{\displaystyle [m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b649f5418f2ac84d66063f41319368b0926ccec4)