Note on Advanced Algorithm I: Fingerprint

检查矩阵乘法正确性 Checking Matrix Multiplication

---

问题描述

给定三个矩阵 $A,B,C\in\mathbb{R}^{n\times n}$，判断 $AB=C$ 是否成立.

如果直接进行矩阵乘法的计算并逐个比较矩阵的元素，时间复杂度为矩阵乘法的复杂度 $O(n^\omega),\text{where}\ \omega>2$，太大了，考虑使用随机算法

Freivald’s Algorithm

选取均匀分布变量 $r\in \{0,1\}^n$，判断 $A(Br)=Cr$ 是否成立，这样时间复杂度为 $O(n^2)$.

下面推导算法的准确性:

当 $AB=C$ 时，$A(Br)=Cr$ 总是成立.

当 $AB\ne C$ 时，考虑 $\mathbb{P}(ABr=Cr)$.

令 $D=AB-C\ne\bold0_{n\times n}$，不妨设 $d_{ij}\ne 0$，则有

$\mathbb P(Dr=\bold{0})\le\mathbb P((Dr)_i=0)=\mathbb P(\sum\limits_{k=1}^nd_{ik}r_k=0)=\mathbb P(r_j=-\dfrac1{d_{ij}}\sum\limits_{k\ne j}d_{ik}r_k)\le\dfrac{2^{n-1}}{2^n}=\dfrac12$

于是运行一次该算法，错误的概率小于$\dfrac12$. 这个概率还是比较大的，可以独立地运行 $O(\log n)$ 次，那么时间复杂度为 $O(n^2\log n)$，错误的概率小于 $\dfrac1{2^{O(\log n)}}$，correct w.h.p

多项式判等 Polynomial Identity Testing (PIT)

---

问题描述

• 给定两个 $d$ 阶多项式 $f,g\in\mathbb F[x]$，判断 $f\equiv g$ 是否成立.
• 给定 $d$ 阶多项式 $f \in\mathbb F[x]$，判断 $f\equiv 0$ 是否成立.

注意多项式都是黑盒的，否则直接比较多项式系数即可.

Randomized Algorithm

选取均匀分布变量 $r\in S,\text{where}\ S\subseteq\mathbb F$，判断 $f(r)=0$ 是否成立.

下面推导算法的准确性:

当 $f\equiv0$ 时，总是成立.

当 $f\not\equiv0$ 时，根据代数基本定理， $d$ 阶多项式 $f \in\mathbb F[x]$ 最多有 $d$ 个根。因此 $\mathbb P(f(r)=0)\le\dfrac{d}{|S|}$。令 $|S|=2d$ 则有 $\mathbb P(f(r)=0)\le\dfrac12$.

跟前一个问题一样，多运行几遍就可以得到正确率较高的结果.

通信复杂性 Communication Complexity

---

问题描述

给定两个实体 $a,b$，他们分别存有 $n$ bit 信息，现在要计算 $f(a,b)$，问所需的通信复杂度，也就是需要传输的 bit 数是多少.

在这里我们讨论 $\text{EQ}:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$
$\text{EQ}(a,b)= \begin{cases} 1 & \text{if}\ a = b\\ 0 & \text{o.w.} \end{cases}$

Deterministic Algorithm

一个简单的确定性算法是将 $b$ 的信息完全传给 $a$，再进行计算，这样的通信复杂度是 $n$ bits.

姚期智证明了所有的确定性算法的最坏通信复杂度是 $n$ bits.

Randomized Algorithm

那能不能利用前面两个问题的思想，使用随机算法来解决呢？

可以将 $a,b$ 的每一位当作多项式系数，$f=\sum\limits_{i=0}^{n-1}a_ix^i,\ g=\sum\limits_{i=0}^{n-1}b_ix^i$，这样就可以转化为 PIT 问题.

根据 PIT，$r\in [2n]$. 对于 $b$ 而言，需要将 $r$ 和 $g(r)$ 传输给 $a$. 传输 $r$ 需要 $O(\log n)$ bits，而 $g(r)=O(r^n)=O(n^n)$，传输 $g(r)$ 需要 $O(n\log n)$ bits，比 $n$ 还大！

在 PIT 中可以注意到 $\mathbb F$ 的取值可以变，可以选择一个更小的域来进行计算，这样通信复杂度可以降下来.

可以选择一个质数 $p \in [n,2n^2]$，令 $f,g\in \mathbb Z_p[x]$，（即模 $p$）

选取均匀分布变量 $s\in[p]$，那么此时误判的概率为 $\dfrac{n-1}{p}=O\left(\dfrac1n\right)$.

传输 $r$ 需要 $O(\log p)=O(\log n)$，传输 $g(r)$ 需要 $O(\log p)=O(\log n)$，因此整体的通信复杂度降到了 $O(\log n)$.

Schwartz-Zippel Theorem

---

问题描述

下面来看更一般的 PIT 问题. 考虑多元多项式 $f\in\mathbb F[x_1,\dots,x_n]\equiv0$ 是否成立

$f(x_1,\dots,x_n)=\sum\limits_{i_1,\dots,i_n\ge0}a_{i_1,i_2\dots,i_n}x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}$

多项式的阶数 $d$ 为 $\max\limits_{a_{i_1,i_2\dots,i_n}\ne 0} i_1+i_2+\cdots+i_n$.

Randomized Algorithm

独立随机选取 $r_1,\dots,r_n\in S$，判断 $f(r_1,\dots,r_n)=0$ 是否成立.

Schwartz-Zippel Theorem 指出

$f\not\equiv0\Rightarrow\mathbb P(f(r_1,\dots,r_n)=0)\le\frac{d}{|S|}$

Proof

$\begin{aligned} f(x_1,x_2,\dots,x_n)&=\sum\limits_{i=0}^dx_n^if_i(x_1,x_2,\dots,x_{n-1})\\ \end{aligned}$

运用数学归纳法：

当 $n=1$ 时，根据之前的结果，成立

假设对于所有小于 $n$ 的情况都成立，令 $k$ 为 $x_n$ 的最高次，也就是说 $f_k\not\equiv0$，$f_k$ 的阶数 $\le d-k$

$\begin{aligned} &\mathbb P(f(r_1,\dots,r_n)=0)\\ =&\mathbb P(f(\bold r)=0|f_k(r_1,\dots,r_n-1)=0)\cdot\mathbb P(f_k(r_1,\dots,r_n-1)=0)\\ &+\mathbb P(f(\bold r)=0|f_k(r_1,\dots,r_n-1)\ne0)\cdot\mathbb P(f_k(r_1,\dots,r_n-1)\ne0)\\ \le&\dfrac{d-k}{|S|}+\dfrac{k}{|S|}=\dfrac{d}{|S|} \end{aligned}$

实际上这也说明了任意 $f\not\equiv0$ 在任意 cube $S^n$ 中的零点 $\le d\cdot |S|^{n-1}$

Fingerprint

---

回到这一章的标题——指纹 fingerprint。以上举的都是几个指纹的例子。指纹是指这样一种函数：

• $a=b\Rightarrow \text{FING}(a)=\text{FING}(b)$
• 若 $a\ne b$, $\mathbb P[\text{FING}(a)=\text{FING}(b)]$ 很小
• $\text{FING}()$ 的值较小

以下介绍几个指纹的例子

通信复杂性

还是这个问题，指纹函数为 $\text{FING}(x)=x\ \mod\ p$，随机选取质数 $p\in[k]$

$\mathbb P[a\equiv b(\mod p)]=\dfrac{\# \text{ of prime divisors of } |a-b|}{\# \text{ of prime in }[k]}\le\dfrac{\log a}{\pi(k)}$

而 $\pi(N)\sim \dfrac{N}{\ln N}$，当 $N\to \infty$. 令 $k=n^3=\log^3 a$，则

$\mathbb P[a\equiv b(\mod p)]\le\dfrac{n\ln k}{k}=O\left(\dfrac1n\right)$

字符串匹配

确定性算法有大名鼎鼎的 KMP 算法。

使用指纹算法，可以依次扫描过去进行对比，使用上一个问题的指纹函数即可

检查集合是否相同

$\text{FING}(A)=f_A(r)=\sum\limits_{i=1}^{n}(x-a_i)$ for uniform random $r \in \mathbb Z_p$, $p\in[(n\log n)^2/2,(n\log n)^2]$

error probability: $O(1/n)$