Combinatorial Shape 的 PRG

[GMRZ11] Pseudorandom Generators for Combinatorial Shapes，阅读笔记。该篇论文给出了种子长度为 $O(\log m + \log n + \log^2 (1 / \varepsilon))$ 的 $(m, n)$-Combinatorial Shape 的 $\varepsilon$-PRG。

主要定理称述

我们先从 Combinatorial Shape 的定义说起：

Definition 1.1. (CShape(m, n)) 称一个函数 $f : [m]^n \to \{0, 1\}$ 是一个 $(m, n)$-Combinatorial Shape (简称 $\text{CShape}(m ,n)$)，若存在 $A_1, \ldots, A_n \subseteq [m]$ 与一个对称函数 $h : \{0, 1\}^n \to \{0, 1\}$，使得 $f(x_1, \ldots, x_n) = h(1_{A_1}(x_1), \ldots, 1_{A_n}(x_n))$。

同时再回顾一下 read-once branching program (ROBP) 的定义：

Definition 1.2. ((S, D, T)-ROBP) 一个 $(S, D, T)$-ROBP $M$ 是一个分层图，其中对于每个 $0 \le i \le T$ 都有一个层，且每层最多有 $2^S$ 个顶点（状态）。第一层包含单个顶点 $v_0$，最后一层中的每个顶点被标记为 $0$（拒绝）或 $1$（接受）。对于 $0 \le i < T$，第 $i$ 层中的顶点 $v$ 恰有 $2^D$ 条出边，每条边标记有 $\{0, 1\}^D$ 中的一个元素，并终止于第 $i + 1$ 层中的一个顶点。

ROBP 非常自然的诱导出一个布尔函数 $M : (\{0, 1\}^D)^T \to \{0, 1\}$。它可以用来建模非常多东西，最经典的就是它可以用来建模空间受限的计算。而在这里，实际上 $(\log n, \log m, n)$-ROBP 也可以用来计算 $\text{CShape}(m, n)$。这是由函数 $h$ 的对称性所带来的，对称性使得 $h(y_1, \ldots, y_n)$ 的值完全由 $(y_1, \ldots, y_n)$ 中有多少个 $1$ 来决定，所以 ROBP 里面的每一层只需要记录 $\sum_{i = 1}^n 1_{A_i}(x_i)$ 的当前值即可。

于是当 $m = \text{poly}(n)$ 时，经典的 Nisan’s 或 INW PRG [Nis92, INW94] 给出了种子长度为 $O(\log^2 n)$ 误差为常数的 PRG。而这篇工作显然给出了一个更加优秀的结果：

Theorem 1.3. 存在一个显式的 $\text{CShape}(m, n)$ 的 $\varepsilon$-PRG，其种子长度为 $O(\log m + \log n + \log^2 (1 / \varepsilon))$。

接下来我们给出 PRG 的构造，该构造分为四步。

两级哈希

方差较小 —— Statistical Distance

方差较大 —— Kolmogorov Distance

对两级哈希进行去随机化

方差较小 —— 利用 Concentration 性质

方差较大 —— 利用 ROBP 的单调性

直和结构

这篇文章探讨一类特殊 ROBP，它们有所谓的单调性质：

Definition 2. (Monotone ROBP)

Theorem 3. 若一个 PRG $G : \{0, 1\}^r \to (\{0, 1\}^D)^T$ 可以 $\delta$-fools $(\log (2 T / \varepsilon), D, T)$-ROBP，则对于任何的 $(S, D, T)$-ROBP，$G$ 都可以 $(\varepsilon + \delta)$-fools 其。

Remark. 该定理非常强，其种子长度与 $S$ 无关。

Proof. 证明应用了所谓离散化的思想。

参考文献

[INW94] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In STOC, pages 356-364, 1994.

[MZ10] Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. In STOC, pages 427-436, 2010.

[Nis92] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449461, 1992.

[NZ96] Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):4352, 1996.