Orthogonal Vectors Problem 相关

  Fine-Grained Complexity 四大基础问题中的一个。

  这里推荐的资料是 MIT 的一门课的第 6、7 讲。

Task

  Orthogonal Vectors Problem (OV)：
  给定 $n$ 个 $d$ 维的 01 向量 $v_1,\cdots,v_n \in \{0,1\}^d$，问是否存在两个向量 $v_i, v_j$ 是正交的，即 $\langle v_i, v_j \rangle = 0$。

  这个问题的暴力是 $O(n^2d)$ 的，枚举两个向量，然后每一维去验证。且在 $d$ 比较小的时候（$d \le 2\log n$ 时），可以用 $O(2^d)$ 的各种算法解决。
  但是在 $d=\omega(\log n)$ 时，我们很难找到 $O(n^{2-\epsilon}d^c)$ 的算法，因此猜想它是 $n^2$-hard 的。事实上，它可以由 SAT 问题归约而来，因此 SAT 的困难性猜想 Strong Exponential Time Hypothesis (SETH) 可以推出 OV 问题的 $n^2$-hardness。

  这个问题有许多变式：

• 给定两个集合 $A,B$，每个集合有 $n$ 个 $d$ 维的 01 向量，问是否存在 $v_1 \in A, v_2 \in B$ 使得 $v_1,v_2$ 正交。（易证这个版本跟上述版本是等价的）
• 计数版本，求有多少对向量是正交的。也可以继续拓展，做近似计数、sampling。
• 不再是 01 向量，而是某个域下的 $d$ 维向量。
• k-OV，给定 n 个向量，问是否存在 k 个向量，内积为 0。困难性猜想为不存在 $O(n^{k-\epsilon})$ 的做法。

比较好的解法

  该解法来自 [AWY15]，可以做到 $O(n^{2-1/O(\log (d/\log n))})$。思路是，给向量分组（每 $s$ 个一组，分为 $\frac ns$ 组），转化成“对于每一个组对 $(A,B)$，是否能在 $A$ 找一个向量，在 $B$ 找一个向量，使其正交”的子问题。每个组对的任务写成一个逻辑公式，并用一些 trick 变成比较好的多项式，然后使用矩阵乘法的 trick 让所有组对同时计算这个多项式。

  先有几个 trick：

Lemma1：如果要计算 $y_1 \lor y_2 \lor \cdots \lor y_m$，那么可以选择一个正整数 $t$，对于每个 $1 \le i \le t$，选择一个随机子集 $s_i \subseteq \{1,\cdots,m\}$，令 $Y_i = \bigoplus_{j \in s_i} y_j$，则只需计算 $Y_1 \lor \cdots \lor Y_t$ 即可。

  证明：
  如果原式为假，则 $Y_1 \lor \cdots \lor Y_t$ 肯定为假。
  如果原式为真，令 $s_{true} = \{y_i | y_i=true\}$，则每次生成随机子集 $s_i$ 时，在 $s_{true}$ 中选中奇数个元素的概率是 $\frac 12$，所以 $P[Y_1 \lor \cdots \lor Y_t=0]=\frac{1}{2^t}$。

Lemma1.5：如果要计算 $y_1 \land y_2 \land \cdots \land y_m$，那么可以选择一个正整数 $t$，对于每个 $1 \le i \le t$，选择一个随机子集 $s_i \subseteq \{1,\cdots,m\}$，令 $Y_i = \lnot \left( \bigoplus_{j \in s_i} \lnot y_j \right)$，则只需计算 $Y_1 \land \cdots \land Y_t$ 即可。

  证明同理，如果原式为真，则 $Y_1 \land \cdots \land Y_t$ 肯定为真；如果原式为假，则 $Y_1 \land \cdots \land Y_t$ 只有 $\frac{1}{2^t}$ 的概率为真。

Lemma2：有一个 $\mathbb F_2$（即模 $2$ 意义）下的多项式 $P(x_1,\cdots,x_d,y_1,\cdots,y_d)$，其展开后是 $m$ 个单项式的和。现有 $n$ 种 $x$ 变量的赋值 $a_1,\cdots,a_n \in \{0,1\}^d$，以及 $n$ 种 $y$ 变量的赋值 $b_1,\cdots,b_n \in \{0,1\}^d$，我们需要对每一对 $(a_i,b_j)$ 都求出 $P$ 的值。若 $m \le n^{0.1}$，这个时间只需要 $\tilde O(n^2)$。

  证明：令矩阵 $M$ 大小为 $n \times m$，$M_{ij}$ 表示第 $j$ 个单项让 $x$ 变量的取值为 $a_i$、$y$ 变量的取值全为 $1$ 时得到的值，同理令矩阵 $N$ 大小为 $m \times n$，$N_{ij}$ 表示第 $i$ 个单项让 $x$ 变量取值全为 $1$、$y$ 变量取值为 $b_j$ 时得到的值，则 $M\cdot N$ 就会得到每一对 $(a_i,b_j)$ 下 $P$ 的值。使用优秀的矩阵乘法技术，当 $m \le n^{0.1}$ 时，矩阵乘法的复杂度只需要 $\tilde O(n^2)$。

  现在可以来做题了。
  先给向量分组，每 $s$ 个一组，分成 $\frac ns$ 组。那么对于每一组，我们要求的东西可以写成一个逻辑表达式：

$$\bigvee_{i,j \in [s]^2} \bigwedge_{k \in [d]} (\lnot v_{ik} \lor \lnot v_{jk})$$

  我们希望把逻辑公式转化为 $\mathbb{F}_2$ 下的多项式，$\land$ 是乘法，$\oplus$ 是加法，$\lnot$ 是加 $1$，$\lor$ 用德摩根律转化为 $a \lor b = (1+a)(1+b)+1$。
  对最外层的或使用德摩根律+Lemma1.5，参数 $t=2$：

$${\Large(} 1+\underbrace{(\bigwedge_{k \in [d]})+(\bigwedge_{k \in [d]})+\cdots+(\bigwedge_{k \in [d]})}_{O(s^2)\text{个}} {\Large)} {\Large(} 1+\underbrace{(\bigwedge_{k \in [d]})+(\bigwedge_{k \in [d]})+\cdots+(\bigwedge_{k \in [d]})}_{O(s^2)\text{个}} {\Large)}+1$$

  对每个 $(\bigwedge_{k \in [d]})$，使用 Lemma1.5，参数 $t=3 \log s$：

$${\Large(} 1+\underbrace{(v_{ik}v_{jk})+(v_{ik}v_{jk})+\cdots +(v_{ik}v_{jk})}_{O(d)\text{个}} {\Large)} {\Large(} 1+()+()+\cdots+() {\Large)} \overbrace{\cdots}^{3 \log s\text{个}} {\Large(} 1+()+()+\cdots+() {\Large)}$$

  这就是我们的多项式 $P$，共 $2sd$ 个变量。给定一个向量组对，通过这个多项式就可以算出这个组对是否有正交向量。By union bound，错误率不高于 $\frac 14+s^2\frac{1}{s^3} = \frac 14+\frac 1s$。
  现在来算一下单项式数量 $m$。把每个 $(\bigwedge_{k \in [d]})$ 展开以后，看上去有 $(d+1)^{3 \log s}$ 个单项，但实际上，每个单项形如 $v_{ik_1}v_{jk_1}v_{ik_2}v_{jk_2}\cdots v_{ik_{3 \log s}}v_{jk_{3 \log s}}$，由于是在 $\mathbb F^2$ 下运算，重复的 $k$ 可以只保留一个，因此这样的单项的数量只有 $\binom{d+1}{3 \log s}$ 个。再把最外层的括号展开，就共有 $m=\left(s^2\binom{d+1}{3 \log s}\right)^2$ 个单项。
  代入 $s=2^{\epsilon \log n / \log (d / \log n)}$，其中 $\epsilon$ 是足够小的常数，~~经过巧妙且艰难的不等式放缩，~~就可以得到：

• 多项式 $P$ 对于单个组对的错误率不高于 $\frac 13$；
• $m \le n^{0.1}$。

  因此就可以用 Lemma2 同时对 $(\frac ns)^2$ 个组对算出 $P$ 的值了，最终只要有一个组对返回 $1$ 那答案就是 $1$。由于现在每个组对的错误率是常数，那么就把整个过程重复 $O(\log n)$ 次（即随机产生多个 $P$），每个组对取众数。By Chernoff bound and union bound，错误率就变成 $\frac{1}{poly(n)}$ 了。

  总结一下，算法流程是

1. 给向量分组，每 $s$ 个一组，共 $\frac ns$ 组；
2. 随机生成多项式 $P$，并写成单项式的和的形式；（$O(m)$）
3. 根据 $P$ 预处理矩阵 $M, N$（矩阵的大小是 $\frac ns \cdot m$ 的）；（$O(\frac ns \cdot m \cdot sd) = O(nmd)$）
4. 计算 $M \cdot N$；（$\tilde O(\frac{n^2}{s^2})$）
5. 重复 2-4，统计每个组对的答案众数。

  时间复杂度分析。瓶颈在于第 4 步，复杂度是 $\tilde O(\frac{n^2}{s^2})$，代入 $s$ 会得到 $\tilde O(n^{2-1/O(\log (d/\log n))})$。重复 2-4 的次数是 $O(\log n)$ 的，对 $\tilde O$ 无影响。
  因此，如果 $d$ 等于常数倍的 $\log n$，那这个算法就是 subquadratic 的了。这也提醒我们在使用 OV 问题的困难性的时候，$d$ 不能太小，必须是 $d=\omega(\log n)$ 的。

  甚至还可以在有解的时候快速求出方案。因为我们锁定了答案在哪个组对里，所以只需要 $O(s^2)$ 暴力就可以了。

Approximate Counting

  然后看 OV 的近似计数版本。
  首先它肯定难于直接判定 OV 有无解，因为 approximate counting 结果是否为 $0$ 就表示了原问题有无解。但是难多少？
  [DL18] 给出了 approximate counting 到 decision 的归约，告诉我们仅是难了 polylog factors。
  由于这篇文章还有很多更 general 的 idea，所以单开一篇写了，看这里。

Average-Case Hardness

  很遗憾，OV 并不是 average-case hard 的，详见 [KW19]。
  就连其计数版本也不是。[DLW20]
  那为什么还要讲 average-case hardess 呢？因为 OV 的一些变式还是 average-case hard 的，比如 OV 计数版本的式子

$$fOV(U,V) = \sum_{i,j \in [n]} \prod_{l \in [d]}(1-u_{il}v_{jl})$$

如果拓展到 $\mathbb F_p$，那就是 average-case hard 的了[BRSV17]。这篇文章普遍被视为 Fine-Grained Cryptography 的开端，正是因为它首先讨论了 average-case hardness。
  以及 [DLW20] 里面一堆奇奇怪怪的变形也是 average-case hard 的。

Completeness

  慢慢填坑。OV 似乎在 First-Oder Problems 中是完全的。具有完全性的问题有很大的价值，比如设计协议，给一个完全问题搞了某种协议以后，这一类问题就都拥有这种协议了。

Reference

• [AWY15] Amir Abboud, Ryan Williams, and Huacheng Yu. More Applications of the Polynomial Method to Algorithm Design. In SODA 2015.
• [BRSV17] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In STOC 2017.
• [DL18] Holger Dell, and John Lapinskas. Fine-grained Reductions from Approximate Counting to Decision. In STOC 2018.
• [DLw20] Mina Dalirrooyfard, Andrea Lincoln, and Virginia Vassilevska Williams. New techniques for proving fine-grained average-case hardness. In FOCS 2020.
• [KW19] Daniel Kane and Ryan Williams. The orthogonal vectors conjecture for branching programs and formulas. In ITCS 2019.