Kushilevitz–Mansour 算法

全部频谱有 $2^n$ 项，但显著系数至多 $1/{\theta }^2$ 个。关键在于无需逐项查找：像搜索一棵二叉树那样，先问半边频谱还有多少质量，再决定是否进入。

如何用两次查询估计一个前缀 ​

把输入分成前 $k$ 位 $u$ 与后 $n-k$ 位 $v$。独立均匀取 $u,u^{\prime },v$，查询 $f(u,v)$ 与 $f(u^{\prime },v)$，计算

固定 $v$ 先对 $u,u^{\prime }$ 平均，再对 $v$ 使用 Parseval，即得 $\mathbb{E}Z=W(\alpha )$。两个查询共享同一个后缀 $v$，这一步正是成员查询带来的能力；普通独立随机样本不会自动提供这样的成对输入。

带误差余量的剪枝步骤 ​

从空前缀开始，逐层扩展为 $\alpha 0,\alpha 1$。对每个子前缀估计 $W$，使加法误差至多 ${\theta }^2/4$，保留估计值至少 $3{\theta }^2/4$ 的节点。只要所有估计准确，任何含有 $\theta$-显著系数的前缀都有真实质量至少 ${\theta }^2$，因此永不被剪掉。

被保留节点的真实质量至少 ${\theta }^2/2$，所以每层最多 $2/{\theta }^2$ 个。实现可设置这个节点上限，超出就报告本次随机估计失败；在全部估计准确的事件上不会触发。到达叶子后，返回的每个系数绝对值至少为 $\theta /\sqrt{2}$，同时包含所有至少 $\theta$ 的系数。

节点上限使总检测数无论估计是否准确，都至多 $B=\lceil 4n/{\theta }^2\rceil$。每个节点使用新的相互独立样本；条件于此前全部历史，$Z\in \{-1,1\}$，Hoeffding 界公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。表明取 $\lceil 32{\theta }^{-4}\log \left(2B/\delta \right)\rceil$ 个样本，就使本次误差超过 ${\theta }^2/4$ 的条件概率至多 $\delta /B$。对最多 $B$ 次检测使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，所有估计同时准确的概率至少 $1-\delta$。每个样本调用两次标签查询，故这份直接实现用

次成员查询，成功概率至少 $1-\delta$。这是便于核对的保守复杂度，不声称最优指数。

三位多数的首层 ​

多数的四个非零系数对应指示串 $100,010,001,111$，每项平方为 $1/4$。首位为 $0$ 的两个项总质量为 $1/2$，首位为 $1$ 的两个项也为 $1/2$。取 $\theta =0.4$，剪枝门槛是 $0.12$，两条首层分支都应保留。继续到叶子便找到三个一次项与一个三次项；算法不会因最后一项次数高就漏掉它。

图按首位拆成上下两棵子树：上半部分以前缀 $0$ 开始，下半部分以前缀 $1$ 开始；二者质量相加为同一个空前缀的质量 $1$。图中使用精确质量，实际算法保留估计值至少为 $0.12$ 的节点。

找出显著系数后，可另用样本估计它们的符号和值，再形成稀疏 Fourier 近似。是否能学好整个函数，还取决于未找出部分的总质量；仅知道每个遗漏系数都小，不保证遗漏项加起来很小。

同一搜索也能处理一个随机标签接口：每次在点 $x$ 返回 $Y_x\in \{-1,1\}$，条件均值为 $h(x)\in [-1,1]$，且每次调用使用新的独立随机币。用两个响应代替前缀估计中的两个函数值，即使查询点碰巧相同，响应也要独立生成；条件乘积的期望才是 $h(u,v)h(u^{\prime },v)$。因此估计仍无偏地得到 $h$ 的前缀平方质量，且 Parseval 总质量 $\mathbb{E}{h}^2\le 1$ 保留了节点数与误差保证。

Goldreich–Levin 归约公理库Goldreich–Levin 硬核位定理Goldreich–Levin theorem把随机内积预测器的平均优势转为好输入比例、带独立随机响应的重Fourier列表及原像验证，完整证明通用硬核位的反演归约。还会把随机内积预测器视为带随机响应的字符查询器，调用这里的显著频谱搜索。在那条密码学归约中，频率索引就是候选原像；仍须证明好输入占比、保证各次响应使用独立随机币，并验证候选的函数像。

BLR 测试公理库BLR 线性测试BLR linearity test · Blum-Luby-Rubinfeld linearity test以三个函数值检查 f(x)+f(y)=f(x+y)，并用 Fourier 一致性证明高通过率函数接近某个线性函数。以三点等式判断是否接近一个线性字符，KM 则输出许多显著频谱位置并依赖主动查询。测试一个性质与重建可学习结构，目标和访问能力都不同。