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$ 组。那么对于每一组,我们要求的东西可以写成一个逻辑表达式:
我们希望把逻辑公式转化为 $\mathbb{F}_2$ 下的多项式,$\land$ 是乘法,$\oplus$ 是加法,$\lnot$ 是加 $1$,$\lor$ 用德摩根律转化为 $a \lor b = (1+a)(1+b)+1$。
对最外层的或使用德摩根律+Lemma1.5,参数 $t=2$:
对每个 $(\bigwedge_{k \in [d]})$,使用 Lemma1.5,参数 $t=3 \log s$:
这就是我们的多项式 $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)}$ 了。
总结一下,算法流程是
- 给向量分组,每 $s$ 个一组,共 $\frac ns$ 组;
- 随机生成多项式 $P$,并写成单项式的和的形式;($O(m)$)
- 根据 $P$ 预处理矩阵 $M, N$(矩阵的大小是 $\frac ns \cdot m$ 的);($O(\frac ns \cdot m \cdot sd) = O(nmd)$)
- 计算 $M \cdot N$;($\tilde O(\frac{n^2}{s^2})$)
- 重复 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 计数版本的式子
如果拓展到 $\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.