从近似程度推导近似秩下界

# 从近似程度推导近似秩下界 ## 1. 近似秩下界与通信应用 ### 1.1 近似秩下界推导 通过一系列公式推导得出近似秩的下界。相关公式如下： - (10.34) - (10.37) 进行了不等式推导，其中 (10.35) 成立是因为对于所有 \(x,y \in \{ -1,1\}^{3n}\)，有 \(R_{xy} \cdot (M_{\psi})_{x,y} > 0\)；(10.36) 成立是由于 \(\psi\) 的平滑性，即对于所有 \(x,y \in \{ -1,1\}^{3n}\)，\(|\psi(x, y)| > 2^d \cdot 2^{-6n}\)；(10.37) 由 \(R\) 的大平均裕度（公式 (10.32)）得出。 - 结合公式 (10.37) 和 (10.33)，可以得出 \(r > 2^{d/2}\)。 ### 1.2 通信应用 - 对于奇偶函数 \(f = \oplus_n\)，其阈值度为 \(n\)，由完美平滑的对偶多项式 \(2^{-n} \cdot \psi\) 见证。由此得到一个具有线性 UPPCC 复杂度的显式通信问题 \(f \circ g\)。 - 推论 10.22 表明，设 \(f = \oplus_n\)，\(F = f \circ g\) 是 \(f\) 与定理 10.20 中的 6 位小工具的组合，则 \(\text{rank}_{\pm}(A_F) > 2^{\Omega(n)}\)，因此 \(\text{UPPCC}(F) > \Omega(n)\)。实际上，根据定理 10.15 的证明，上述下界对于内积函数也成立，恢复了 Forster 的突破性结果。 ## 2. AC0 函数的 UPPCC 下界 ### 2.1 问题提出 之前的函数 \(f \circ g\) 不在 AC0 中。几十年来，一直存在一个开放问题：是否存在一个 AC0 函数 \(F\)，使得 \(\text{UPPCC}(F) > \text{polylog}(n)\)。这个问题最初由 Babai、Frankl 和 Simon 以不同但等价的形式提出，即是否存在一个函数 \(F\)，可以由具有多对数成本的 PHCC 协议解决，但不能由具有多对数成本的 UPPCC 协议解决。 ### 2.2 问题解决 Razborov 和 Sherstov 解决了这个问题，他们证明了 Minsky - Papert CNF \(AND_{n^{1/3}} \circ OR_{n^{2/3}}\) 具有阈值度 \(\Omega(n^{1/3})\) 的平滑对偶见证的存在性。 ### 2.3 显式构造 我们希望为 AC0 函数构造一个显式的平滑对偶见证。虽然 Minsky - Papert DNF 已有相关构造，但我们基于 [50] 中的技术给出一个更容易理解的构造。不过，我们的对偶见证 \(\Delta\) 稍微达不到应用定理 10.20 所需的平滑性。但我们能够为 AC0 函数 \(AND_{n^{1/3}} \circ OR_{n^{2/3}} \circ \oplus_{\log_2 n}\) 获得一个平滑对偶见证 \(\xi\)，足以得出 UPPCC 下界。 #### 2.3.1 定理 10.23 设 \(f = AND_{n^{1/3}} \circ OR_{n^{2/3}} \circ \oplus_{\log_2 n}\)，定义在 \(N = n \log_2 n\) 个变量上。则 \(\text{deg}_{\pm}(f) > D\)，其中 \(D = \Omega(n^{1/3} \log n)\)。此外，存在一个对偶多项式 \(\xi\)，使得对于所有 \(x \in \{ -1,1\}^N\)，\(\xi(x) \cdot f(x) > 2^{-\Omega(n)} \cdot 2^{-N}\)。 #### 2.3.2 证明步骤 - **构造平滑对偶见证 \(\Delta\)**：首先构造一个平滑对偶见证 \(\Delta\)，用于证明 \(\text{deg}_{\pm}(AND_{n^{1/3}} \circ OR_{n^{2/3}}) > d\)，其中 \(d > \Omega(n^{1/3} / \log n)\)。但 \(\Delta\) 不够平滑，定理 10.20 要求 \(|\Delta(x)| > 2^{d/2}2^{-n}\)，而 \(\Delta\) 仅满足 \(|\Delta(x)| > 2^{-\Omega(n)} \cdot 2^{-n}\)。 - **构造对偶见证 \(\xi\)**：为 \(f\) 构造一个对偶见证 \(\xi\)，其平滑性与 \(\Delta\) 相同，但见证了稍大的度下界 \(D = d \log_2 n\)。因此，\(\xi\) 相对于其见证的度界足够平滑，可以应用定理 10.20。 #### 2.3.3 Minsky - Papert CNF 的平滑对偶多项式 - 设 \(m = n^{1/3}\)，从定理 7.10 中构造的对偶见证开始，其中 \(g = OR_{n^{2/3}}\)，\(F = AND_m \circ g\)。该定理构造的对偶多项式 \(\mu^{(m)}\) 存在两个问题：一是存在符号错误，即对于某些输入 \(x\)，\(\text{sgn}(\mu^{(m)}(x)) \neq F(x)\)；二是不光滑。 - 我们将修改这个见证，消除符号错误并使其平滑。具体步骤如下： 1. **步骤 1：在小汉明重量输入上实现大值** - 设 \(x^* = (x_1^*, \cdots, x_n^*) \in (\{ -1,1\}^{n^{2/3}})^m\) 是汉明重量至多为 \(w\) 的输入，选择 \(w = \Omega(m / \log m)\)，使得 \(n^w < 2^{m/2}\)。 - 构造对偶见证 \(\gamma_{x^*}\)，满足 \(\gamma_{x^*}(x^*) > (7/8)^m\)，\(\gamma_{x^*}(x) > 0\) 对于所有 \(|x| < m\)，并且 \(\gamma_{x^*}\) 见证了 \(\text{deg}_{1 - 4^{-m}}(F) > d\)。 - 最终的对偶多项式 \(\gamma(x) = \frac{1}{M} \sum_{x^*} \gamma_{x^*}(x)\) 见证了 \(\t