查询复杂度的对偶多项式见证

形式陈述

设 $f:D\to\{0,1\}$ ， $D\subseteq\{0,1\}^n$ ，令 $V_d$ 是所有次数至多 $d$ 的实多项式限制到 $D$ 后形成的有限维线性空间。近似次数满足

\widetilde{\deg}_\varepsilon(f)>d

当且仅当存在函数 $\psi:D\to\mathbb R$ ，使

\sum_{x\in D}|\psi(x)|=1,

并且对每个 $p\in V_d$ 都有

\sum_{x\in D}\psi(x)p(x)=0,

同时

\sum_{x\in D}\psi(x)f(x)>\varepsilon.

可把 $\psi$ 整体乘 $-1$ ，所以最后一个相关性不等式无需绝对值。第二个条件称 pure high degree 大于 $d$ ；在 $\{-1,+1\}$ 编码中，只需检查所有 $|S|\le d$ 的 Fourier character

\chi_S(z)=\prod_{i\in S}z_i.

有限维线性规划强对偶给出该刻画。Primal 在系数中寻找 $p$ ，约束每个合法输入上 $|p(x)-f(x)|\le\varepsilon$ ；dual 选择有符号权重 $\psi$ 。若三个条件成立，则任意 $p\in V_d$ 都满足

\sum_x\psi(x)f(x) =\sum_x\psi(x)(f(x)-p(x)) \le\sum_x|\psi(x)|\,\|f-p\|_\infty \le\varepsilon,

与严格相关性矛盾。反方向由 separating hyperplane 定理得到，故见证不仅充分而且完备。

直觉

Primal 试图让低次多项式同时穿过所有误差带；dual 则给输入点加正负质量，把每个低次方向完全抵消，却让目标函数仍留下可见偏置。一个短向量 $\psi$ 因而能替代“枚举所有低次多项式”的不可能任务。

一范数归一不是装饰。若没有它，可把任意非零相关性无限放大；若只要求均值为零，则仅消除了常数项，线性、二次等低次方向仍可能解释目标。Pure high degree 必须逐层消去全部 $V_d$ 。

例子与边界

对 $\operatorname{OR}_2$ ，按 $00,01,10,11$ 顺序定义

\psi=\left(-\frac12,\frac14,\frac14,0\right).

它的一范数为 $1$ ，总和为 $0$ ，所以与全部次数 $0$ 的常数多项式正交。OR 的值为 $(0,1,1,1)$ ，相关性为

\langle\psi,\operatorname{OR}_2\rangle =\frac14+\frac14 =\frac12>\frac13.

因此 $\widetilde{\deg}_{1/3}(\operatorname{OR}_2)>0$ 。另一方面线性多项式 $p=(2/3)(x_1+x_2)$ 在四点上的值为 $0,2/3,2/3,4/3$ ，最大误差为 $1/3$ ；两边合起来得到近似次数恰为 $1$ 。见证的每个约束和上界多项式都可直接复算。

Promise 域是见证的一部分。若把域限制为所有非零输入，OR 恒为 $1$ ，常数多项式已经精确计算它；上面的 $\psi$ 在非法点 $00$ 放了负质量，不能继续作为该 promise 的 dual。把 total-function 见证机械截断到合法域通常也会破坏正交。

编码也需一致。 $0/1$ 与 $\pm1$ 通过仿射替换保持次数，但相关性阈值和目标函数会相应变换；不能保留 $\psi$ 数值却只替换公式一侧的编码。

推论与应用

对偶见证把 approximate-degree 下界变成可组合对象：可以对已有 $\psi$ 做张量、块组合或质量重分配，同时单独验证一范数、pure high degree 与相关性。量子查询多项式方法再把这样的代数证书翻译为查询下界。

见证只证明没有低次一致逼近，不证明查询算法上界，也不控制多项式系数大小。若错误是 one-sided、平均 $L_2$ 或 sign approximation，primal 约束改变，dual 条件也必须重新推导。

参考资料

Mark Bun and Justin Thaler, “Dual Lower Bounds for Approximate Degree and Markov–Bernstein Inequalities,” Information and Computation 243, 2015, pp. 2–25.
Alexander A. Sherstov, “Communication Lower Bounds Using Dual Polynomials,” Bulletin of the EATCS 95, 2008, pp. 59–93.
Alexander A. Sherstov, “The Pattern Matrix Method,” SIAM Journal on Computing 40(6), 2011, pp. 1969–2000.

形式陈述 ​

反向链接

形式陈述