布尔（Boolean）函数的傅里叶分析
对比普通函数的傅里叶分析，我们试图将傅里叶分析的思想迁移到布尔函数上。傅里叶分析找到一组正交基（Orthogonal Basis）。我们在布尔函数上也能找到这样的基。具体来说，令
$$\chi_i\left(x\right) = \prod\limits_{j \in i}x_j$$
，选系统 $\chi_i : i \subseteq \left[n\right]$ 作为正交基。
于是我们就可以用这组正交基进行傅里叶分析：
$$f = \sum\limits_{i \subseteq \left[n\right]}\hat f\left(i\right)\chi_i$$
，其中 $\hat f\left(i\right) \in \mathbb R$。
Blum-Luby-Rubinfeld 线性性测试
对于布尔函数 $f : \left\{0, 1\right\}^n \to \left\{1, -1\right\}$，我们可以使用以下方法来测试该函数的线性性。
- 随机选择 $x, y \in \left\{0, 1\right\}^n$
- 如果 $f\left(x + y\right) = f\left(x\right) + f\left(y\right)$，该算法认为这是具有线性性的函数。
我们现在评估该算法的正确性。
首先，我们要定义该函数离线性性函数的距离 $\epsilon$。
我们这里采用的距离函数为：
$$\operatorname{dist}\left(f, g\right) = \Pr\limits_{i}\left[g\left(i\right) \neq f\left(i\right)\right]$$
我们发现，这个距离有很好的性质：
$$ \begin{aligned} \left\langle f, g\right\rangle &= \mathbb E_{x \sim \left\{1, -1\right\}^n}\left[f\left(x\right)g\left(x\right)\right]\\ &= \Pr\left[f\left(x\right) = g\left(x\right)\right] - \Pr\left[f\left(x\right) \neq g\left(x\right)\right]\\ &= 1 - 2\operatorname{dist}\left(f, g\right) \end{aligned} $$
若 $f$ 不具有线性性，BLR 的错误概率不高于 $1 - \epsilon$，实际可能更低。
分析方式如下
$$ \begin{aligned} \Pr\left[\text{BLR accepts f}\right] &= \mathbb E_{x, y}\left[\frac12 + \frac12f\left(x\right)f\left(y\right)f\left(x + y\right)\right]\\ &= \frac12 + \frac12\mathbb E_x\left[f\left(x\right)\mathbb E\left[f\left(y\right)f\left(x + y\right)\right]\right]\\ &= \frac12 + \frac12\mathbb E_x\left[f\left(x\right)\widehat{f * f}\left(x\right)\right]\\ &= \frac12 + \frac12\sum\limits_S\hat f\left(S\right)\widehat{f * f}\left(S\right)\\ &= \frac12 + \frac12\sum\limits_S\hat f\left(S\right)^3\\ &\leq \frac12 + \frac12\max\limits_S\hat f\left(S\right)\sum\limits_S\hat f\left(S\right)^2\\ &= \frac12 + \frac12\max\limits_S\hat f\left(S\right) \end{aligned} $$
对比 $1 - \epsilon$：
$$ \begin{aligned} 1 - \epsilon &\leq \frac12 + \frac12\max\limits_S\hat f\left(S\right)\\ 1 - 2\epsilon &\leq \max\limits_S\hat f\left(S\right) \end{aligned} $$
$$\hat f\left(S\right) = \left\langle f, \chi_S \right\rangle = 1 - 2\operatorname{dist}\left(f, \chi_S\right)$$
$\exists S$ s.t. $\operatorname{dist}\left(f, \chi_S\right) \leq \epsilon$。
单位影响力
设 $Inf_i\left(f\right)$ 表示 $f$ 上第 $i$ 位的影响力。
$x^{\oplus i}$ 表示将 $x$ 的第 $i$ 位取反，以及 $f^{\left(i\right)}\left(x\right) = f\left(x^{\oplus i}\right)$。
$$ \begin{aligned} Inf_i\left(f\right) &= \Pr_x\left[f\left(x\right) \neq f\left(x^{\oplus i}\right)\right]\\ &= \operatorname{dist}\left(f, f^{\left(i\right)}\right)\\ &= \frac12 - \frac12\left\langle f, f^{\left(i\right)}\right\rangle\\ &= \frac12 - \frac12\left(\sum\limits_{S : i \in S}\hat f\left(S\right)^2 - \sum\limits_{S : i \notin S}\hat f\left(S\right)^2\right)\\ &= \frac12\left(\sum\limits_{S : i \in S}\hat f\left(S\right)^2 + \sum\limits_{S : i \notin S}\hat f\left(S\right)^2\right) - \frac12\left(\sum\limits_{S : i \in S}\hat f\left(S\right)^2 - \sum\limits_{S : i \notin S}\hat f\left(S\right)^2\right)\\ &= \sum\limits_{S \ni i} \hat f\left(S\right)^2 \end{aligned} $$
对布尔函数施加噪声
噪声操作 $T_{\rho}f\left(x\right) = \mathbb E_{y \sim \rho^x}\left[f\left(y\right)\right]$，$y$ 是随机变量，
$$y \sim \rho^x: y_i = \begin{cases}x_i & \text{w.p.} \rho\\\text{uniformly random} & \text{w.p.} 1 - \rho\end{cases} = \begin{cases}x_i & \text{w.p.} \frac{1 + \rho}2\\-x_i & \text{w.p.}\frac{1 - \rho}2\end{cases}$$
据此有
$$ \begin{aligned} T_{\rho}\chi_S\left(x\right) &= \mathbb E_{y \sim \rho^x}\left[\chi_S\left(y\right)\right] = \mathbb E_{y \sim \rho^x}[\prod\limits_{i \in S}y_i]\\ &= \prod\limits_{i \in S}\mathbb E_{y_i \sim \rho^{x_i}}\left[y_i\right] = \prod\limits_{i \in S}\rho x_i \\ &= \rho^{\lvert S \rvert}\chi_S\left(x\right) \end{aligned} $$
所以
$$T_{\rho}f = T_{\rho}\left(\sum\limits_S\hat f\left(S\right)\chi_S\right) = \sum\limits_S\rho^{\lvert S \rvert}\hat f\left(S\right)\chi_S$$
参考
https://box.nju.edu.cn/d/feb7035e412948b5b909/files/?p=%2F%E5%A7%9A%E9%B9%8F%E6%99%96.pptx
https://arxivtools.blob.core.windows.net/xueshuxiangzipaperhtml/2024_4_2/2404.00084.pdf
https://www.cs.purdue.edu/homes/hmaji/teaching/Spring%202019/lectures/33.pdf