PCP 8 — Expanders: tiết kiệm random bits và khuếch đại gap

8.f. Sơ lược về các kết quả xây dựng một họ expanders

Định nghĩa. (Họ expanders)

Cho trước các hằng số $d,\alpha>0$ , một chuỗi các đồ thị $\{G_i\}_{i=1}^\infty$ là một họ $(d,\alpha)$ của các spectral expanders nếu $G_i$ là $(n_i,d,c)$ -spectral expander. Trong đó, $n_1<n_2<\dots$ , và tồn tại một đa thức $g(n)$ sao cho $n_{i+1} = O(g(n_i))$ với mọi $i$ . Điều kiện cuối cùng này chỉ để giới hạn kích thước của các expanders trong họ. Cái sau không thể có kích thước bằng số mũ của cái trước.

Trong đa số các ứng dụng (xem dưới đây), cho trước một hằng số $\alpha<1$ , chúng ta muốn là có một hằng số $d$ sao cho một họ $(d,\alpha)$ của các spectral expanders tồn tại, và mỗi thành viên trong họ có thể xây dựng được trong polynomial time.

Định nghĩa. (Họ expanders xây dựng tương đối cụ thể)

Một họ $\{G_i\}$ của các expanders có thể xây dựng được một cách tương đối cụ thể (mildly explicit) nếu tồn tại một thuật toán mà cho input là $i$ nó output đồ thị $G_i$ trong thời gian $\text{poly}(i)$ .

Ví dụ: có thể xây dựng một họ các expanders như sau. Gọi $n_i$ là số nguyên tố thứ $i$ . Đặt $V(G_i) = \mathbb Z_{n_i}$ (nhóm Abel). Với một đỉnh bất kỳ $x \in \mathbb Z_{n_i}$ thì nối $x$ với các hàng xóm $x+1,x-1,x^{-1}$ . Trong đó, các phép tính cộng, trừ, nghịch đảo là tính trên nhóm. Và, ta định nghĩa nghịch đảo của $0$ là $0$ . Đáng lẽ, ta có thể xây dựng đồ thị thứ $i$ rất nhanh, nhưng vì không biết cách nào để sinh số nguyên tố thứ $i$ ngoài cách cơ bắp (thử từng số từ $1$ trở đi và dùng thuật toán AKS), cho nên tổng thời gian chạy để sinh ra đồ thị thứ $i$ là $\text{poly}(i)$ .

Định nghĩa. (Họ expanders xây dựng rất cụ thể)

Một họ $\{G_i\}$ của các expanders có thể xây dựng được một cách rất cụ thể (strongly explicit) nếu tồn tại một thuật toán mà cho input là $i$ , đỉnh $v \in [n_i]$ , và số $k \in [d]$ , thuật toán in ra hàng xóm thứ $k$ của đỉnh $v$ trong đồ thị $G_i$ trong thời gian $\text{poly}(\log i, \log n_i, \log d)$ (đại khái là thời gian đa thức trong tổng số bits để biểu diễn bộ ba $(i,n_i,d)$ .

Ví dụ: Grigory Margulis (giải Fields năm 1978) chứng minh từ hồi 1973 rằng họ đồ thị xây dựng như sau là một họ expanders. Đặt $V(G_n) = \mathbb Z_n \times \mathbb Z_n$ . Định nghĩa

$\displaystyle T_1 = \begin{bmatrix} 1&2\\0&1\end{bmatrix},T_1 = \begin{bmatrix} 1&0\\2&1\end{bmatrix},e_1 = \begin{bmatrix} 1\\0\end{bmatrix}, e_2 = \begin{bmatrix}0\\1\end{bmatrix}$

Trong đồ thị thứ $n$ $G_n$ , đỉnh $v$ sẽ được nối với $4$ đỉnh $T_1v, T_2v, T_1v+e_1,T_2v+e2$ (và sẽ có $4$ đỉnh khác nối với nó dùng định nghĩa này). Vì thế, đây là đồ thị $8$ -regular. Gabber và Galil hồi năm 1981 chứng minh rằng đây là họ $(8, 5\sqrt 2/8)$ các spectral expanders, có thể xây dựng được một cách rất cụ thể như trên. Nếu có thời gian và hứng thú tôi sẽ duyệt qua chứng minh này dùng phương pháp của Jimbo và Marouka hồi năm 1987 (dùng giải tích Fourier).

Ví dụ: Alon và Boppana khoảng năm 1990 chứng minh được rằng, nếu $G$ là một đồ thị $d$ -regular thì $\hat\lambda(G) \geq \frac{2\sqrt{d-1}}{d} - o_n(1)$ . Do đó, với một họ $(d,\alpha)$ spectral expanders ta chỉ có thể hy vọng là $\alpha = \frac{2\sqrt{d-1}}{d}$ là tối ưu rồi. (Đây là tối ưu về mặt eigenvalue, nhưng không nhất thiết là tối ưu về edge/vertex expansion rate.) Lubotzky-Phillips-Sarnak hồi 1988 xây dựng một họ các đồ thị đạt đến ngưỡng này. Các đồ thị này gọi là các đồ thị Ramanujan. Phép xây dựng của họ có tính rất cụ thể. Họ đồ thị mà họ xây dựng là các Cayley graphs của một họ các nhóm tuyến tính tổng quát. Quyển sách nho nhỏ dễ thương này là giới thiệu tốt về Ramanujan graphs: Elementary Number Theory, Group Theory and Ramanujan Graphs (London Mathematical Society Student Texts).

Ví dụ: Gần đây, tích zig-zag là một cách khác nữa để xây dựng một cách rất cụ thể một họ expanders. Chúng ta sẽ định nghĩa và chứng minh kết quả vừa đạt giải thưởng Godel năm 2008 này trong bài tới.

Định lý. (Xây dựng expander mạnh từ expander yếu.)

Nếu có thể xây dựng được một họ $(d,\alpha)$ các spectral expanders trong đó $d, \alpha<1$ là các hằng số, thì cho trước $0<\beta<1$ nhỏ tùy ý, tồn tại hằng số $d'$ sao cho ta cũng xây dựng được một họ $(d',\beta)$ các spectral expanders.

Chứng minh. Gọi latex $G^k$ là lũy thừa bậc $k$ của đồ thị $G$ , nghĩa là $uv \in E(G^k)$ nếu và chỉ nếu khoảng cách giữa $u$ và $v$ trong $G$ nhiều nhất là $k$ . Dễ thấy rằng adjacency matrix của $G^k$ là ${\bf A}^k$ , trong đó ${\bf A}$ là adjacency matrix của $G$ . Do đó, $\hat \lambda(G^k) = (\hat\lambda(G))^k$ . Chỉ cần chọn $k$ sao cho $(\hat\lambda(G))^k \leq \beta$ là xong!

QED

8.g. Tiết kiệm random bits dùng expanders

$\mathsf{coRP}$ là lớp các bài toán (hay ngôn ngữ) $L$ sao cho, tồn tại một thuật toán ngẫu nhiên hóa $A$ chạy trong poly-time thỏa mãn điều kiện sau đây:

nếu $x\in L$ thì $\text{Prob}[A \text{ accepts } x] = 1$
nếu $x \notin L$ thì $\text{Prob}[A \text{ accepts } x] \leq 1/2$

Để giảm xác suất lỗi của thuật toán $A$ xuống, phương pháp đơn giản nhất là chạy $A$ $t$ lần độc lập, và chấp nhận $x$ nếu và chỉ nếu cả $t$ lần $A$ đều chấp nhận $x$ . Khi đó, nếu $x \notin L$ thì $\text{Prob}[A \text{ accepts } x] \leq 1/2^t$ , nghĩa là xác suất lỗi đã được giảm theo hàm mũ. Điểm bất lợi của phương pháp “lặp tuần tự” (sequential repetition) này là, nếu tổng số random bits mà $A$ cần trong một lần chạy là $r$ bits, thì tổng số random bits cần dùng là $tr$ .

Dùng expanders, chúng ta có thể giảm tổng số random bits cần dùng xuống mà vẫn giảm được xác suất lỗi của $A$ theo hàm mũ. Giả sử ta xây dựng được (một cách rất cụ thể) một $(2^r, d, \alpha)$ -spectral expander với $d, \alpha<1$ là các hằng số. Mỗi một đỉnh của expander này được "dán nhãn" là một chuỗi $r$ bits. Vì thế, có thể xem mỗi đỉnh của expander như một chuỗi random bits để tặng cho thuật toán $A$ . Nếu chúng ta chọn $t$ đỉnh ngẫu nhiên, độc lập nhau, và đưa chúng cho $A$ thì kết quả như trước. Ý tưởng “lặp dùng expander” là: thay vì chọn $t$ đỉnh ngẫu nhiên độc lập nhau, thì ta chọn $t$ đỉnh ngẫu nhiên bằng cách chọn một khởi điểm ngẫu nhiên và bước $t-1$ bước ngẫu nhiên. Dùng các đỉnh gặp dọc đường làm chuỗi ngẫu nhiên cho $A$ chạy. Cuối cùng, vẫn chấp nhận $x$ nếu và chỉ nếu $A$ luôn chấp nhận $x$ trong cả $t$ lần này. Tổng số bits ngẫu nhiên ta dùng là $r + t\log_2d$ . Do $d$ là hằng số, tổng số bits ngẫu nhiên trở nên tuyến tính trên hai tham số $t,r$ , thay vì $tr$ như trong cách lặp tuần tự.

Trực quan là: do random walk trên expanders mau chóng hội tụ đến trạng thái cân bằng là phân bố đều, lấy mẫu bằng random walk cũng gần tốt bằng lấy mẫu hoàn toàn ngẫu nhiên, độc lập.

Khi $x \in L$ thì $A$ luôn chấp nhận $x$ bất kể random walk của ta là gì. Khi $x \notin L$ , gọi $B$ là tập các chuỗi ngẫu nhiên làm cho $A$ chấp nhận $x$ . Do $\text{Prob}[A \text{ accepts } x] \leq 1/2$ , ta có $|B| \leq \frac 1 2 2^r$ . Xác suất mà $A$ chấp nhận $x$ chính là xác suất mà cái random walk của ta bị “giam cầm” trong $B$ trong toàn bộ $t-1$ bước. Từ bài trước, xác suất này $\leq \sqrt{1/2} ( \alpha + (1-\alpha)/2 )^{t-1}$ cũng giảm theo hàm mũ!

8.h. Khuếch đại gap dùng expanders

Ý tưởng trong mục 8.g. cũng dùng được để chứng minh một kết quả khó xấp xỉ mạnh hơn cho bài toán Max-Clique. Nhớ rằng, trong bài PCP 3 chúng ta đã chứng minh rằng, nếu $\mathsf{NP} \subseteq \mathsf{PCP}_{c,s}[r,q]$ và nếu $2^{r+q} = \text{poly}(n)$ , thì chúng ta không thể xấp xỉ Max-Clique đến tỉ lệ $s/c+\epsilon$ với bất kỳ $\epsilon>0$ nào.

Từ định lý PCP, ta biết rằng tồn tại một $(O(\log n), O(1))$ -restricted verifier cho $\mathsf{NP}$ với completeness $1$ và soundness $1/2$ . Dùng expander như trong mục 8.g và lập lại verifier này $t$ lần, chúng ta có thể giảm soundness xuống còn $s = \sigma^t$ với $\sigma<1$ là một hằng số . Completeness vẫn bằng $1$ . Tổng số query bits ta dùng là $q = tO(1)$ . Tổng số random bits ta dùng là $r = O(\log n) + t \log d$ . Do đó, để giữ cho $2^{r+q} = \text{poly}(n)$ , ta có thể lập lại verifier đến $t = \log_2 n$ (hoặc bất kỳ một hằng số nào nhân với $\log_2n$ lần).

Như vậy, ta kết luận rằng không thể xấp xỉ Max-Clique đến tỉ lệ $s/1 + \epsilon = \sigma^{\log_2n}+\epsilon$ với mọi $\epsilon$ . Có một điểm hơi tinh tế cần chú ý là, khi viết tỉ lệ khó xấp xỉ, ta phải viết nó thành hàm số của kích thước instance của bài toán Max-Clique. Tổng số đỉnh của đồ thị trong FGLSS reduction là $N = 2^{r+q}$ . Dễ thấy rằng $\sigma^{\log_2n} = 1/N^\delta$ với $\delta >0$ là một hằng số. Do đó, ta kết luận rằng

Định lý.

Trừ phi $\mathsf{P=NP}$ , tồn tại một hằng số $\delta>0$ sao cho không thể xấp xỉ Max-Clique đến tỉ lệ $1/N^\delta + \epsilon$ với mọi $\epsilon>0$ .

Kết quả trên rất mạnh, là vì thuật toán ngu xuẩn xuất ra một đỉnh đã có tỉ lệ xấp xỉ là $1/N$ . Sau này, chúng ta sẽ chứng minh rằng xấp xỉ Max-Clique đến tỉ lệ $1/N^{1-\epsilon}$ là không thể được (trừ phi $\mathsf{P=NP}$ ) với mọi $\epsilon>0$ cho trước.

8.i. Tiết kiệm random bits cho các thuật toán “lỗi hai bên”

Có một điểm khá tinh tế là ý tưởng “lặp tuần tự” hoặc “lặp dùng expanders” để giảm xác suất lỗi sẽ không áp dụng trực tiếp được cho các thuật toán bị lỗi hai bên; hoặc cho các PCP verifiers không có completeness bằng $1$ .

$\mathsf{BPP}$ là lớp các ngôn ngữ $L$ sao cho, tồn tại một thuật toán ngẫu nhiên hóa $A$ chạy trong poly-time thỏa mãn điều kiện sau đây:

nếu $x\in L$ thì $\text{Prob}[A \text{ accepts } x] \geq 2/3$
nếu $x \notin L$ thì $\text{Prob}[A \text{ accepts } x] \leq 1/3$

Để giảm lỗi (ở cả hai phía — cả false positives lẫn false negatives), chúng ta cần một thuật toán khác, không thể đơn giản chỉ “lặp lại $t$ lần và chấp nhận $x$ nếu $A$ chấp nhận $x$ toàn bộ $t$ lần”. (Bài tập: ta gặp khó khăn gì khi dùng chiến lược đơn giản này?)

Trước hết, chiến lược “lặp tuần tự” cho trường hợp lỗi hai bên này là chạy $A$ $t$ lần độc lập, với $t$ lẻ, và chấp nhận $x$ nếu và chỉ nếu $A$ chấp nhân trong đa số các lần chạy; không chấp nhận $x$ trong trường hợp ngược lại. Để phân tích thuật toán “bầu cử dân chủ” này, chúng ta cần biết chặn Chernoff — một trong những bất đẳng thức hữu dụng nhất trong lý thuyết xác suất.

Chặn Chernoff.

Cho các biến ngẫu nhiên $X_1, \dots, X_t$ trong đó $\text{Prob}[X_i = 1] = p$ và $\mbox{Prob}[X_i = 0] = 1-p$ , với $p$ là một xác suất cho trước. Dễ thấy rằng $\mathbb{E}\left[ \sum_{i=1}^t X_i \right] = tp.$ Các chặn Chernoff cho ta ước lượng xác suất mà $\sum_{i=1}^tX_i$ nằm xa giá trị kỳ vọng $tp$ . Phân bố của tổng này có hai cái “đuôi” mỏng ở hai đầu, còn lại tập trung vào gần trị kỳ vọng (giống như hình ngọn núi), gọi là hiện tượng concentration.

Với mọi $\delta \in (0,1)$ , chặn Chernoff cho đuôi trên (upper tail) có thể viết như sau:

$\displaystyle \mbox{Prob}\left[\sum_{i=1}^tX_i \geq (1+\delta)tp\right] \leq e^{-tp\delta^2/3}$
và cho đuôi dưới (lower tail) ta có
$\displaystyle \mbox{Prob}\left[\sum_{i=1}^tX_i \leq (1-\delta)tp\right] \leq e^{-tp\delta^2/2}$
Nói theo ngôn ngữ phổ thông thì: khi $t$ tiến ra vô cùng, khả năng mà $\sum_{i=1}^tX_i$ nằm xa trung tâm tiến đến $0$ theo hàm mũ (exponentially reduced).

Để dùng chặn Chernoff, xét trường hợp $x \in L$ trước. Đặt $X_i=1$ nếu thuật toán $A$ không chấp nhận $x$ trong lần chạy thứ $i$ , $1 \leq i \leq t$ ; ngược lại thì gán $X_i=0$ . Gọi $p$ là xác suất mà $A$ không chấp nhận $x$ . Ta có $p = \text{Prob}[X_i = 1] \leq 1/3$ . Thuật toán “bầu cử dân chủ” không chấp nhận $x$ nếu và chỉ nếu $\sum_i X_i \geq t/2$ . Do đó, xác suất mà $x \in L$ không được chấp nhận cũng giảm theo hàm mũ:

$\displaystyle \text{Prob}\left[ \sum_{i=1}^t X_i \geq t/2 \right] \leq \text{Prob}\left[ \sum_{i=1}^t X_i \geq (1+1/2)tp \right] \leq e^{-tp(1/2)^2/3}$

Phân tích tương tự cho thấy khi $x \notin L$ , xác suất nó được chấp nhận (false positive) cũng giảm theo hàm mũ. Như vậy, nếu chiến lược là lặp tuần tự thì chúng ta có thể giảm xác suất lỗi theo hàm mũ như trong trường hợp “lỗi một bên” kiểu $\mathsf{coRP}$ . Và cũng như trong trường hợp lỗi một bên, tổng số random bits dùng sẽ là $tr$ , hơi quá lớn cho một số ứng dụng.

Có thể nào áp dụng phương pháp “lặp dùng expanders” cho trường hợp lỗi hai bên được không? Như trong phân tích trên, chúng ta cần chặn xác suất mà một random walk gồm $t$ bước bị giam cầm trong $B$ trong ít nhất một nửa số bước. Cái random walk này có thể đi vào $B$ và đi ra khỏi $B$ nhiều lần, miễn là tổng số bước nằm trong $B$ ít nhất là $t/2$ . Định lý trong mục 8.e (bài PCP 7) quá yếu cho mục tiêu này. Tuy nhiên, chúng ta có thể sửa lại chứng minh định lý 8.e một chút để có định lý sau đây:

Định lý (Khó “giam cầm” random walk trên expander ở một tập các bước cố định).

Cho trước một tập $B$ các đỉnh, $|B| \leq \beta n$ của một $(n,d,\alpha)$ -spectral expander $G$ , một số nguyên dương $t$ , và một tập con $K\subseteq \{0,1,\dots,t\}$ . Gọi $(B,K,t)$ là sự kiện mà cái random walk gồm $t$ bước trên $G$ bị giam giữ trong tập $B$ trong toàn bộ các bước trong tập $K$ . (Nghĩa là, nếu $K=\{0, 3, 4, 6\}$ thì đỉnh khởi điểm, đỉnh ở bước ngẫu nhiên thứ $3, 4, 6$ nằm trong $B$ , còn các đỉnh khác trong $t-1$ bước ta không quan tâm.) Ta có,

$\displaystyle \text{Prob}\left[(B,K,t)\right] \leq (\alpha + (1-\alpha)\beta)^{|K|-1}.$

Bài tập: chứng minh định lý trên. (Gợi ý: gần giống hệt chứng minh định lý “giam cầm” kia.)

Bài tập: dùng định lý trên để phân tích chiến lược “lặp dùng expanders” cho một thuật toán lỗi hai phía.

Tóm lại, với expanders ta có thể khuếch đại gap cho cả trường hợp không có completeness bằng $1$ . Bài tới viết về một phương pháp xây dựng rất cụ thể các họ expanders: phương pháp dùng zig-zag product mới được giải Godel.

PCP 8 — Expanders: tiết kiệm random bits và khuếch đại gap

Post a Comment

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Toán học

Vật Lý