终于把大研的中期报告胡过去了，听说没有人看，于是就写的简单点。
正好也好久没发博客，就把文献调研部分拿出来发一个，记录一下这学期读的部分文章。因为大研报告的提交平台的富文本编辑器不支持公式，所以这里也就都没有用 latex，凑合看吧[doge]
研究问题
Learing Parity with Noise 的问题描述如下：
- 有一个隐藏的，长度为 n 的 0/1 向量 s, 目标是找出它
- 我们可以对数据库进行若干次询问，每次询问，会得到如下的回答：
- 一个长度为 n 的随机 0/1 向量 y
- x dot y mod 2 的结果（但是会以 eta 的概率被翻转，即噪音）
上述 Setting 比较难，有时候我们会添加一些额外的限制条件，比如：
- Sparse： s 中 1 的数量不超过k
- Low-noise：eta = n ^ Omega(1)
- Structured-noise：多个样本上的噪音分布可以用一个多项式描述
当 eta = 0 的时候，上述问题退化成可以直接用高斯消元在 O(n^3) 时间内解决。
文献调研
一般情况
在 eta 是常数的情况下，如果继续使用高斯消元，因为每个答案都由 O(n) 个样本线性组合而成，答案的正确率会随着 n 增加而指数衰减。
BKW03
BKW 算法的想法是：让最终的答案由尽可能少 (比如 n^0.5 个) 的向量线性组合而成
具体做法：
- 将向量分为 a 个长度为 b 的块，要求一次消元将一块内的 entries 全消成 0，这样答案仅仅由 2 ^ a 个向量构成
- 这样算出的答案正确率可能也仅比 0.5 多出 Omega(1) ^ (2 ^ a)，但是上述算法可以同时产生很多个答案，再对答案进行一次 majority vote 即可大概率找出真正的答案
取 a = O(log n)，上述算法的时间和采样复杂度都是 2 ^ O(n / log n)
最简单的算法是 O(2^n) 枚举 s，随后就可以在询问得到的数据集上验证枚举的结果是否正确。
Lyu05
当限制采样复杂度是多项式级别时，Lyubashevsky 修改了 BKW 算法，使其时间复杂度变成了 2 ^ O(n / loglog n), 而采样复杂度降低为 n ^ (1 + epsilon)
Sparse
Sparse 情形下最简单的算法是花费 (n choose k) = (n / k) ^ k 的时间枚举 s, 随后在样本上验证。
Valiant
Sparse 情况的大多数算法都基于 Biased Sample, 即：虽然样本中的向量每一位都以 0.5 的概率为 0/1, 但是在计算时保留 1 较多的样本。这样就可以认为向量的每一位都以大于0.5 的某个概率 p 为 1 。
这样的好处是，在枚举答案时，不用把所有 k 个 1 的位置全部枚举出来，就可以获得关于 s 的一些线索，比如：当前枚举的这些位置和真正的答案交集大小。
Valiant 的算法大致是先枚举出所有大小为 k/3 的子集，然后基于快速矩阵乘法找到两个这样的子集，使得他们拼起来最接近 s. 其时间复杂度是 n ^ (0.8k)，采样复杂度是 Omega(k ^ 2)。
BKW meets Fourier
这篇文章使用 BKW 和 高斯消元 主动生成 Biased Sample, 随后基于布尔函数的傅里叶分析得到了一些结论。最终的结果是在 k 在 n / log n 或者 n eta 附近的时，可以达到 (n / k) ^ o(k) 的复杂度。
Sparse & Low-noise
GRV11
这篇文章的想法是枚举大小为 k/2 的子集，随后用两个这样的子集拼出 s。容易发现，正确的两个子集，与所有样本中 y 点乘的结果一定是高度相似的。利用这一点，可以用 Locality Sensitivity Hashing 快速找出满足两个符合要求的子集，复杂度大约是 n ^ ((1+O(eta))k/2).
(此后也调研了一些关于 LSH 的文章，在此略过)
YYL21
这篇文章对不同参数的 LSPN 问题进行了一些规约，同时也给出了一个 (eta n)^2k 的 LSPN 算法。
Structured-noise
AG11
这篇文章给出了一个与噪音分布多项式的度数 m 相关的算法，其复杂度是 poly(n ^ m). 其中主要用了 linearization 的技巧。
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: