【STOC2018】Fine-grained Reductions from Approximate Counting to Decision

  这篇文章给了些很不错的思路，把一些问题的 approximate counting 版本归约到 decision 版本上，更具体地说，如果给定 decision 版本的 oracle，就能在很小的时间代价内（比如对于 OV 等问题是 polylog）完成 approximate counting。该方法适用于 k-SAT、OV、3-SUM 等 Fine-Grained Complexity 关注的核心问题。

Idea

  这个思路 high level 来讲就是“减半”，对某个东西不停地减半，直到能暴力为止。
  k-SAT 和其他问题（OV、3-SUM、Negative-Weight-Triangle）做法稍有不一样，这里会有两种不同的“减半”思路。

k-SAT

  k-SAT 问题的“减半”思路是这样的：给 k-SAT 问题增加额外的条件，使得解数减半，直到解数足够少，能通过“暴力搜够一定的解数就停”来求出。

  先看怎么把解数减半。
  假设原题是给定一个公式 $F$，求有多少个解 $x$（$x$ 看成是 $n$ 维 01 向量），使得 $x \models F$。现在增加一个矩阵 $A$，大小为 $m \times n$（$m \le n$），$A$ 的每一行里随机选择 $s$ 个元素，这 $s$ 个元素独立随机地选择 $0$ 或 $1$，其余元素都是 $0$；再增加一个 $n$ 维 01 向量 $b$，每个元素都是独立随机。然后把原题的要求变成 $x \models F$ 且 $Ax=b$（$\mathbb F_2$ 下运算）。
  $A$ 的每一行相当于随机选 $s$ 个元素然后对它们的异或和作出限制，由于 $b$ 是随机的，原题的每个解满足一行限制的概率是 $\frac 12$，满足 $m$ 行的概率就是 $\frac{1}{2^m}$。根据期望的线性性，

$$\begin{aligned} \mathbb E[\text{新的解数}] = \sum_{x \models F} \text{Pr}[Ax=b] = \frac{\text{原来的解数}}{2^m}. \end{aligned}$$

  也就是 $A$ 的每一行都使得解数减半，$m$ 行就减成原来的 $\frac{1}{2^m}$。
  但只有期望减半是不够的，还要 with high probability 能减半，也就是还要一个 concentration。这里用的是 Chebyshev 不等式，也就是要 bound 住它的方差。方法大约是把 $\mathbb E[(\text{新的解数})^2]$ 用期望线性性拆成每个解对单独考虑，然后把解对用 Hamming Distance 大小分成两组，分别 bound 住。这里比较琐碎和炫技，就不详述，可以自行看论文。
  （我感觉 $A$ 的每一行选出 $s$ 个元素之后直接把它们都赋值为 $1$ 就好了，不需要再独立随机，方差甚至能更小。）

  然后再来看“暴力搜够一定解数就停”，比如要求搜够 $a$ 个解就停。这里就要用到 decision oracle 了。
  首先，$Ax=b$ 这个限制可以变为长度为 $m2^{s-1}$ 的 $s$-CNF（$A$ 的每一行相当于规定把至多 $s$ 个变量 xor 起来的值，用 $2^{s-1}$ 个 CNF clause（可由 not DNF clause 转化而来）来枚举表示），所以原公式 $F$ 加上这个限制可以归约成 $\max(k,s)$-SAT。
  暴力如下：枚举第一个变量为 $0$，用 oracle 判断是否有解，有就递归下去；完了之后枚举第一个变量为 $1$，用 oracle 判断是否有解，有就递归下去。搜够 $a$ 个解之后就返回（返回解数，或“解数大于 $a$”）。复杂度 $O(a)$。

  所以整体方法就出来了：设定一个阈值 $a$，从小到大枚举 $m$，对于每个 $m$ 重复多次实验，如果“暴力搜够 $a$ 个解就停”算法返回确切解数，那么就乘 $2^m$ 然后输出，否则继续下一个 $m$。

  正确设置参数大小，可使得最后时间复杂度为：对于任意 $\delta>0$ 以及 multiplicative error $\epsilon$，时间复杂度为 $\epsilon^{-2} \cdot O(2^{(\Delta+\delta)n})$，其中 $O(2^{\Delta n})$ 是 decision oracle 的复杂度。
  （我感觉这个 $m$ 甚至不用从小到大枚举，可以二分，不过鉴于复杂度是指数的，对于 $poly(n)$ 的优化似乎并不重要。。。）

二分图边数

  给定一个二分图，左右总共 $n$ 个点，你要近似出它的边数。你只有两种 oracle 来访问这个图，一是直接询问某一对点之间是否有边，二是选定一个点集问这个点集是否包含边（这一般就对应 decision oracle）。
  OV、3-SUM、Negative-Weight-Triangle 都可以归约到这个问题，所以我们只要解决这个问题就好。

  这个问题的“减半”思路是这样的：假如这个图的一侧（假设是 $V$ 侧，另一侧是 $U$）比较平衡（即不会有少数点集中了大部分的边），那么这一侧随机选一半的点，也会使得边数减半。减下去直到点数变为 $O(\log n)$，就可以 $\tilde O(n)$ 暴力了。

  Formally 来说，我们主要考虑 $V$ 侧，定义平衡为存在一个 $\xi \in (0,1)$，每个点的度数都不超过 $\xi$ 倍的总边数（或者说归一化后度数不超过 $\xi$），称之为 $\xi$-平衡。先假设我们知道每个点的度数。
  如果 $V$ 侧的点是 $\xi$-平衡的，那么对 $V$ 侧的点进行伯努利采样，期望会留下一半的点，边数也会变成原来的约一半。这一步的证明是简单的 concentration 应用，使用 McDiarmid 不等式。
  那如果不平衡呢，也就是 $V$ 有少数点比较菊花。解决办法就是把归一化度数超过 $\frac{\xi}{2}$ 的点拉出来放入点集 $S$，对 $U \times S$ 做 Simple Random Sampling（Chernoff bound 保证概率，并且 $|S|$ 不会很大，否则 $V$ 会平衡），剩下的 $V \setminus S$ 的点要么是度数都在 $\xi N(V \setminus S)$ 以内（$N(X)$ 表示 $X$ 的临集），也就是平衡的；要么存在点度数超过 $\xi N(V \setminus S)$，但是它不在 $S$ 里说明它度数不超过 $\frac{\xi}{2} N(V)$，联立起来就是 $N(V \setminus S) \le \frac 12 N(V)$，即剩下的点在 $U$ 的临集大小会减半。
  （我这样写是把原文的参数简化了，便于理解）

  这里需要做两件事：1、估计出 $V$ 里每个点的度数；2、万一不平衡或者 $N(V)$ 太小需要暴力，则需要把 $N(V)$ 也找出来。
  我们可以用一个算法同时解决这两件事：设一个阈值 $y$，将 $U$ 侧的点随机打乱，每次操作用二分 + decision oracle 判定的方法找到一个 $V$ 的临集点，直到找不到了或者找满 $y$ 个点就停。这样返回的结果，如果临集大小在 $y$ 以内，就会返回精确的临集，否则会返回一个大小为 $y$ 的临集的采样。
  这个采样即可用来估计 $V$ 侧的点的归一化后的度数，准确率由 Chernoff bound 保证。

  所以整体算法是这样的：如果 $V$ 侧只有 $O(\log n)$ 大小，或者设定阈值 $y=\text{poly}(\log n)$ 用上述算法发现 $N(V) \le y$，那么就暴力，否则用刚才得到的 $N(V)$ 的大小为 $y$ 的采样估计出每个点的归一化度数，如果是平衡的，则对 $V$ 进行伯努利采样，递归，否则挑出 $S$，对 $U \times S$ 进行 Simple Random Sampling，对 $V \setminus S$ 递归。

  时间复杂度，可以看到每次递归下去，要么 $V$ 大小减半（期望减半，with high probability 减到 $\frac 34$），要么 $N(V)$ 大小减半，且 $V$ 的大小不会增大，所以最多递归 $\log^2 n$ 层。每层要做的就是二分 + decision oracle 判定去做采样，做 $y=\text{poly}(\log n)$ 次。所以总复杂度是 $O(\epsilon^{-2} \cdot poly(\log n) \cdot \Delta)$，其中 $\Delta$ 是 decision oracle 的时间。

Fine-Grained Complexity 核心问题

• #OV 归约到二分图边数：左边 $n$ 个点表示 $n$ 个向量，右边 $n$ 个点表示 $n$ 个向量，两个点之间有边当且仅当它们正交。第一个 oracle 就是直接判定两个向量是否正交，第二个 oracle 就是框定一个子问题判断是否存在正交。
• #3-SUM 归约到二分图边数：左边一排点表示第一个数集，右边一排点表示第二个数集，两个点之间有边当且仅当它们的和的相反数存在于第三个数集。第一个 oracle 就是直接判定两个数的和的相反数是否存在于第三个数集，第二个 oracle 就是框定一个子问题判断是否存在三个数和为 $0$。
• #NWT 归约到二分图边数：左边一排点表示原图的点，右边一排点表示原图的边，两个点之间有边当且仅当原图这个点和边能组成负权三角形。第一个 oracle 就是直接判定一个三角形是否负权，第二个 oracle 就是框定一个子图问是否存在负权三角形。

吹水时间

  其实要读过论文才知道，虽然减半这个思路很厉害，但是真正主体的工作，是怎样用 concentration 来 bound 住这些减半，如果 bound 不住那么这就只是拍个脑袋而已了。还是得好好学 concentration，多积累不等式啊。。。