双块组合的硬度放大与意外应用

# 双重块组合在硬度放大及近似度下界中的应用 ## 1. 双重块组合的硬度放大定理 ### 1.1 相关定理介绍 - **定理 7.8**：设 \(f:\{-1,1\}^m \to \{-1,1\}\) 是一个对称布尔函数，\(g\) 是任意函数，则有 \(deg(f \circ g) \cdot \log m > \Omega(deg(f) \cdot deg(g))\)。该定理并非使用对偶多项式方法证明，而是间接依赖于 Belovs 提出的用于组合群测试的复杂量子算法。 - **定理 7.9**：设 \(g\) 是一个布尔函数，且 \(deg_{1/2}(g) > d\)，\(F = \oplus_m \circ g\)，则 \(deg_{1 - 2^{-m}}(F) > \Omega(m \cdot d)\)。该定理表明通过组合可以增加误差，Sherstov 证明此定理的技术与定理 7.7 本质相同，使用了双重块组合的改进方法来构造对偶见证。 - **定理 7.10**：设 \(g\) 是一个布尔函数，且 \(odeg_{1/2}(g) > d\)，\(F = AND_m \circ g\)，则 \(deg_{1 - 2^{-m}}(F) > d\)。 - **定理 7.11**：设 \(g\) 是一个布尔函数，且 \(odeg_{1/2}(g) > d\)，\(F = AND_m \circ g\)，则 \(deg_{\pm}(F) > \min\{d, m\}\)。 ### 1.2 定理 7.10 的证明 为证明定理 7.10，我们定义一个简单的对偶见证： - 令 \(\psi(1^m) = \frac{1}{2}\)，\(\psi(-1^m) = -\frac{1}{2}\)，\(\psi(x) = 0\)（其他情况）。 - 设 \(\phi\) 是 \(odeg_{1/2}(f) > d\) 的任意对偶见证。 - 我们声称 \(\psi * \phi = \frac{1}{2} \cdot (\psi_+ \phi_+ - \psi_- \phi_-)\) 见证了 \(deg_{1 - 2^{-m}}(F) > d\)。 - 根据定理 7.3，\(\psi\) 的 \(l_1\) - 范数为 1。 - 根据定理 7.2 以及 \(phd(\psi) > 1\) 和 \(phd(\phi) > d\) 的事实，\(\psi * \phi\) 具有纯高次 \(d\)。 为了证明 \((\psi * \phi, AND_m \circ g) > 1 - 2^{-m}\)，关键在于对 \(E(z) = Pr[(AND_m \circ g)(x) \neq AND_m(\psi)]\) 进行上界估计，其中 \(z = -1^m, 1^m\) 是 \(|\psi|\) 的支撑集内的两个点： - **情况 1：\(z = 1^m\)**：仅当 \(g(x_1) = g(x_2) = \cdots = g(x_m) = -1\) 时，\((AND_m \circ g)(x) \neq AND_m(\psi)\)。由于 \(\phi\) 与 \(g\) 的相关性至少为 \(\frac{1}{2}\)，所以 \(\phi_+(g^{-1}(-1)) < \frac{1}{2}\)。因此，对于 \(z = 1^m\)，表达式 \(E(z)\) 至多为 \(2^{-m}\)。 - **情况 2：\(z = -1^m\)**：因为 \(\psi\) 是 \(g\) 的单边近似度的对偶见证，\(\phi_-\) 的支撑集是 \(g^{-1}(-1)\) 的子集，所以 \(\psi * \phi\) 的支撑集是 \((AND_m \circ g)^{-1}(-1)\) 的子集。因此，对于 \(z = -1^m\)，表达式 \(E(z)\) 为 0。 ### 1.3 定理 7.11 的相关说明 定理 7.11 可以在定理 7.10 的构造基础上进行证明，通过向 \(\psi * \phi\) 中添加一个纯高次为 \(m\) 的额外“修正项” \(\xi\)，使得 \(\psi * \phi - \xi\) 与 \(AND_m \circ g\) 完全相关。 ### 1.4 定理应用：统计零知识的神谕分离 - **定义 GAPMAJ 函数**：定义 \(GAPMAJ_m:\{-1,1\}^m \to \{-1,1\}\) 为一个部分函数，当至少 \(\frac{2}{3}\) 的输入为 \(-1\) 时，\(GAPMAJ_m\) 等于 \(-1\)；当至少 \(\frac{2}{3}\) 的输入为 \(+1\) 时，\(GAPMAJ_m\) 等于 \(+1\)；否则未定义。 - **定理 7.12**：设 \(f\) 是一个布尔函数，且 \(deg_{1/3}(f) > d\)，\(F = GAPMAJ_m \circ f\)，则 \(deg_{1 - 2^{-\Omega(m)}}(F) > d\) 且 \(deg_{\pm}(F) > \Omega(\min\{d, m\})\)。 - **神谕分离的证明**：Bouland 等人使用定理 7.12 展示了一个神谕 \(O\)，使得 \(SZK^O \neq PP^O\)。证明步骤如下： 1. 回顾查询复杂度的概念，使用标准的对角化论证，只需在类似的查询复杂度模型中建立分离即可。 2. 要获得一个神谕 \(O\) 使得 \(SZK^O \neq PP^O\)，只需找到一个 \(F\)，使得 \(SZK_{dt}(F) = O(\log n)\) 且 \(PP_{dt}(F) = \Omega(n)\)。 3. \(SZK_{dt}