PCP 9 — Expanders: tích zig-zag

8.j. Tích zig-zag

Chúng ta đã thấy rằng đã số các ứng dụng của expanders không những cần sự tồn tại của expanders mà còn cần thuật toán xây dựng expanders hiệu quả (hoặc tương đối cụ thể, hoặc rất cụ thể). Bài này viết về một phương pháp/thuật toán hiệu quả để xây dựng expanders một cách rất cụ thể gọi là tích zig-zag. Quan trọng hơn, phương pháp này tiềm ẩn những ý tưởng áp dụng được vào các bài toán khác, như trong chứng minh {\mathsf{L=SL}} sẽ trình bày trong bài tới, hoặc trong bản thân chứng minh định lý PCP của Dinur sẽ trình bày sau.

8.j.1. Trực quan

Tạo một expander tốt không khó khăn gì, ví dụ như {K_n} là expander tốt nhất có thể có. Nhưng tạo expander thưa, với constant degree, thì khó. Một ý tưởng tự nhiên là thử tìm cách xây dựng một expander lớn từ một số các expanders nhỏ hơn sao cho không làm tăng degree quá đáng thì ta có hy vọng. Ví dụ, một cách xây dựng expander lớn từ expander nhỏ là “bình phương” cái expander nhỏ: {\hat\lambda(G^2) = \hat\lambda^2(G)}. Cái dở là ta không thể “nhân” với {G} mãi được vì degree cũng bị bình phương luôn.

Tích zig-zag là một cách xây dựng một expander lớn từ hai expanders nhỏ hơn. Cụ thể là, cho trước {G}{H}{(n,m,\alpha)}-spectral expander và {(m,d,\beta)}-spectral expander, theo thứ tự. Chúng ta sẽ xây dựng một đồ thị mới, ký hiệu là {G \textcircled{z} H}, gọi là “tích zig-zag” của {G}{H}. Tích này sẽ là một {(mn, d^2, f(\alpha,\beta))}-spectral expander, trong đó cái spectral expansion rate mới {f(\alpha, \beta)<1} nếu {\alpha<1}{\beta<1}. Nôm na là, nếu {G}{H} là expanders thì {G \textcircled{z} H} cũng là expander.

Ta sẽ chứng minh được rằng {f(\alpha,\beta)\leq \alpha +\beta+\beta^2} (đây là chặn trên cụ thể, còn {\alpha,\beta<1} vẫn suy ra {f(\alpha,\beta)<1} nhưng đó không phải là chặn trên cụ thể). Từ đó, nếu ta bắt đầu bằng một đồ thị {H}{(d^4,d, 1/5)}-spectral expander (Bài tập: chứng minh tồn tại bằng phương pháp xác suất), thì ta có thể xây dựng một họ các expanders như sau:

  • {G_1 = H^2}
  • {G_2 = G_i^2 \textcircled{z} H}

Dễ thấy rằng đây là một chuỗi vô hạn các expanders. Đồ thị {G_i} là một {(d^{4i}, d^2, 2/5)}-spectral expander. Có thể cải tiến cái chặn trên {\alpha+\beta+\beta^2} được, nhưng điều đó không quan trọng. Xem thêm bài báo tích zig-zag nguyên thủy của Reingold, Vahdan, và Wigderson.

Bây giờ ta mô tả {G \textcircled{z} H}. Chú ý rằng degree của {G} bằng tổng số đỉnh của {H}. Trước hết, với mỗi đỉnh {v} của {G}, đặt tên các cạnh xung quanh {v} bằng các đỉnh của {H} một cách tùy hỉ. Xem hình dưới đây, tôi đã đặt tên các cạnh xung quanh v, u, w.

zigzag

Mỗi đỉnh của {G \textcircled{z} H} là một cặp đỉnh {(u,v) \in V(G) \times V(H)}. Có thể hình dung tập đỉnh của {G \textcircled{z} H} được chia thành {n} “đám mây”, mỗi đám mây là một nhân bản của {H} (cạnh màu xanh lá cây). Sau đó, ta nối một đỉnh của đám mây này đến một đỉnh của đám mây khác nếu đỉnh này là tên của đầu này của cạnh và đỉnh kia là tên ở đầu kia của cạnh. Ví dụ, trong hình thì ở {G} có cạnh {wv} với tên ở đầu {w}{2} và tên ở đầu {v}{1}, ta nối đỉnh {2} trong đám mây của {w} với đỉnh {1} trong đám mây của {v} bằng một cạnh màu đen.

Nếu ta chỉ giữ các cạnh màu xanh lá cây và cạnh màu đen, thì ta có cái gọi là “tích thay thế” (replacement product). Degree của tích thay thế là {d+1}. Ta có thể chứng minh được tích thay thế cũng là expander. Tuy nhiên, về mặt kỹ thuật sẽ tiện hơn nếu ta thêm {d} cạnh song song cho mỗi cạnh của {G}; ví dụ như sẽ có {d} cạnh song song giữa đỉnh {2} trong đám mây của {w} và đỉnh {1} trong đám mây của {v}. Kết quả là một đồ thị với degree {2d}, cũng thường được gọi là tích thay thế hoặc tích thay thế cân bằng (balanced replacement product). Bài này (SODA 2007) của Alon, Schartz, và Shapira dùng tích thay thế này để xây dựng expanders (constant degree). Phép xây dựng này của Alon et al. cũng là một combinatorial construction, nhưng nó xuất hiện 6, 7 năm sau zig-zag; ngoài ra phép zig-zag cũng đóng vai trò quan trọng trong việc phát triển trực quan cho các kết quả khác, do đó chúng ta nói về tích zig-zag.

Quay lại với xây dựng tích zig-zag: các cạnh màu xanh và cạnh màu đen không phải là các cạnh của {G \textcircled{z} H}. Nếu ta có thể đi từ một đỉnh {x} của {G \textcircled{z} H} đến một đỉnh {y} của {G \textcircled{z} H} bằng cách thăm {3} cạnh: xanh-đen-xanh, thì ta nối {x} với {y} thành một cạnh của {G \textcircled{z} H}. (Vì thế mới gọi là tích zig-zag.) Trong hình, các cạnh màu đỏ mới là các cạnh của tích {G \textcircled{z} H}. Tôi chỉ vẽ ví dụ vài cạnh màu đỏ, vẽ hết sẽ cực rối.

Như vậy, một bước ngẫu nhiên trên {G \textcircled{z} H} bao gồm một bước ngẫu nhiên màu xanh trong một “đám mây” {H}, một bước xác định (deterministic) qua một cạnh đen của {G}, và một bước ngẫu nhiên (màu xanh) khác trong đám mây bên kia của {H}. Về mặt trực quan, chúng ta phải chứng minh rằng ba bước này làm cho phân bố các đỉnh trở nên gần cân bằng (uniform) hơn. (Nhớ góc nhìn xác suất của expanders.) Mỗi một đỉnh của {G \textcircled{z} H} là một cặp đỉnh {(g, h)}, với {g} là một đỉnh của {G}{h} là một đỉnh của {H}. Đỉnh {(g,h)} sẽ gần uniform nếu mỗi tọa độ là gần uniform và độc lập với nhau. Giả sử ta bắt đầu từ một phân bố mà phân bố của {h} (bên trong đám mây) là xa uniform (entropy thấp), thì bước ngẫu nhiên màu xanh đầu tiên sẽ làm cho phân bố của {h} gần uniform hơn vì {H} là expander. Hai bước còn lại thì một bước là xác định, và một bước ngẫu nhiên trên {H} sẽ không làm giảm độ uniform của phân bố của {h}. Còn nếu phân bố của {h} đã là uniform thì bước một bước vẫn giữ nó uniform, trong khi đó phân bố của {g} sẽ trở nên uniform hơn vì bước màu đen (cùng với bước màu xanh đầu) sẽ tương tự như một bước ngẫu nhiên trên {G}. Tuy nhiên, vì các cạnh đen thực sự là một matching của các đỉnh của {G \textcircled{z} H}, do đó nếu ta tăng entropy của (phân bố của) {g} thì sẽ làm giảm entropy của {h}. Do đó, ta cần bước màu xanh thứ {3} để tăng lại entropy của {h}. (Vì thế, bài zig-zag nguyên thủy có chữ “entropy wave” trong đó.) Chứng minh dưới đây theo trực quan này.

8.j.2. Định nghĩa cụ thể và phân tích

Với mỗi đỉnh {u \in V(G)}, đặt tên các cạnh kề với {u} theo thứ tự tùy ý là {e_u^1, \dots, e_u^m}. Đồ thị {G \textcircled{z} H} được xây dựng như sau:

  • {V(G \textcircled{z} H) = \{(u,i) \ | \ u\in V(G), i \in [m]=V(H)\}}.
  • Có một cạnh nối {(u,i)} với {(v,j)} nếu và chỉ nếu tồn tại {k, l \in [m]} sao cho {ik \in E(H)}, {e_u^k = e_v^l}, và {lj \in E{H}}.

Dễ thấy rằng {G \textcircled{z} H}{mn} đỉnh và (regular) degree {d^2}. Gọi {\mathbf{\hat A}, \mathbf{\hat B}} là các normalized adjacency matrices của {G, H}, theo thứ tự. Định nghĩa một ma trận {mn \times mn} đặt tên là {\mathbf P} như sau: {p_{(u,k),(v,l)} = 1} nếu và chỉ nếu {e_u^k = e_v^l}. Lưu ý rằng {\mathbf P} là một ma trận hoán vị đối xứng (symmetric permutation matrix). Định nghĩa ma trận {\mathbf{\tilde B} = \mathbf I_n \otimes \mathbf{\hat B}} (trong đó {\otimes} là ký hiệu của tensor product của hai ma trận).

Bài tập: chứng minh rằng {\mathbf M = \mathbf{\tilde B P \tilde B}} chính là normalized adjacency matrix của tích zig-zag {G \textcircled{z} H}.

Từ đó, ta có

\displaystyle  f(\alpha,\beta) = \max_{\mathbf{x \perp u}} \frac{|\langle \mathbf{\tilde B P \tilde B x, x} \rangle|}{\langle \mathbf{x, x} \rangle}.

Xét một vector {\mathbf{x \perp u}, \mathbf x \in \mathbb R^{mn}} tùy ý. Định nghĩa một “vector thu thập” {C(\mathbf x) \in \mathbb R^n} như sau: {C(\mathbf x)_u = \frac 1 m \sum_{i\in [m]} x_{(u,i)}}. Nói cách khác, tọa độ thứ {u} của {C(\mathbf x)} là giá trị trung bình của các tọa độ {x_{(u,i)}} trong “đám mây” thứ {u} của vector {\mathbf x}. Đến đây, định nghĩa các thành phần song song và vuông góc:

\displaystyle  \mathbf x^{\|} := C(\mathbf x) \otimes \mathbf 1_m

trong đó {\mathbf 1_m \in \mathbb R^m} là vector mà tất cả các tọa độ đều bằng {1}; và,

\displaystyle  \mathbf x^\perp = \mathbf x - \mathbf x^\|

Xét vector {\mathbf x \perp \mathbf u}, chúng ta muốn chứng minh rằng {|\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq f(\alpha, \beta) \langle \mathbf{x,x} \rangle}. Hãy bắt đầu với vế trái trước. Lưu ý rằng, do {\mathbf x^\|} “phân bố đều” trên mỗi “đám mây”, ta có {\mathbf{\tilde Bx^\| = x^\|}}. (Bài tập: chứng minh điều này.)

\displaystyle  |\langle \mathbf{\tilde B P \tilde B (x^\|+x^\perp), (x^\|+x^\perp)} \rangle| \leq |\langle \mathbf{Px^\|, x^\|} \rangle| + 2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| + \|\mathbf{\tilde Bx^\perp} \|^2

Xét số hạng cuối cùng. Do vector {\mathbf x^\perp} “phản phân bố đều” trên mỗi “đám mây” (nghĩa là tổng của các tọa độ của {\mathbf x^\perp} trên từng đám mây là bằng {0}), ta suy ra rằng {\|\mathbf{\tilde Bx^\perp}\| \leq \beta \|\mathbf x^\perp\|}.

Kế tiếp, ta chặn số hạng thứ hai. Do {\mathbf P} là một ma trận hoán vị, nó không thay đổi norm của một vector. Ta có:

\displaystyle  2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| \leq 2\| \mathbf{P\tilde Bx^\perp}\| \|\mathbf{\tilde B x^\|}\| \leq 2\beta \| {\bf x}^\perp\| \|{\bf x}^\|\|

Cuối cùng, ta chặn số hạng thứ nhất.

Bài tập: chứng minh rằng

\displaystyle  \langle \mathbf{Px^\|, x^\|} \rangle = m \langle \mathbf{\hat A} C(\mathbf x), C(\mathbf x)\rangle \leq m\alpha \|C(\mathbf x)\|^2 = \alpha \|\mathbf x^\|\|^2

Vì thế,

\displaystyle  |\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \alpha \|\mathbf x^\|\|^2 + 2\beta \| {\bf x}^\perp\| \|{\bf x}^\|\|  + \beta^2 \|\mathbf x^\perp\|^2

Lưu ý rằng {\|\mathbf x\|^2 = \|\mathbf x^\|\|^2 + \|\mathbf x^\perp\|^2}. Ta suy ra

\displaystyle  |\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \max(\alpha+\beta, \beta+\beta^2)\|\mathbf x\|^2 \leq (\alpha+\beta+\beta^2)\|\mathbf x\|^2

Như vậy, ta vừa chứng minh được định lý sau đây:

Định lý 1 (Định lý zig-zag)

Nếu {G} là một {(n,m,\alpha)}-spectral expander và {H} là một {(m,d,\beta)}-spectral expander thì tích zig-zag {G \textcircled{z} H} là một {(mn, d^2, \alpha+\beta+\beta^2)}-spectral expander.

8.j.3. Xây dựng rất cụ thể (chạy trong thời gian poly-log)

Theo như cách mô tả xây dựng họ expanders ở trên, thời gian cần để xây dựng đồ thị {G_i}{\text{poly}(|V(G_i)|)}. Muốn một họ expanders được xây dựng một cách rất cụ thể (định nghĩa trong bài PCP 8), thì ta cần phép xây dựng này chạy trong thời gian poly-log. Ý tưởng chính là dùng phương pháp tương tự như “repeated squaring”.

Trước hết, cần định nghĩa tích tensor của hai đồ thị. Gọi {G_1=(V_1,E_1)} là một {d_1}-regular graph với {n_1} đỉnh, {G_2=(V_2,E_2)}{d_2}-regular graph với {n_2} đỉnh. Tích tensor {G_1 \otimes G_2} được định nghĩa như sau: {V(G_1 \otimes G_2) = V_1 \times V_2}, và hai đỉnh {(u_1,u_2)}{(v_1,v_2)} là kề nhau nếu và chỉ nếu {u_1v_1\in E_1}{u_2v_2\in E_2}.

Bài tập: chứng minh rằng nếu {G_1}{G_2}{(n_1,d_1,\alpha_1)}-spectral expander và {(n_2,d_2,\alpha_2)}-spectral expander, theo thứ tự, thì {G_1 \otimes G_2}{(n_1n_2,d_1d_2, \max(\alpha_1,\alpha_2))}-spectral expander. (Gợi ý: normalized adjacency matrix của đồ thị tích là tích tensor của hai normalized adjacency matrices.)

Từ đó, có thể xây dựng họ expanders như sau. Gọi {H} là một {(d^8,d,\alpha)}-spectral expander với các hằng số {d,\alpha<1} nào đó. Sau đó, định nghĩa

  • {G_1 = H^2}
  • {G_2 = H \otimes H}
  • {G_n = \left(G_{\left\lceil\frac{n-1}{2}\right\rceil} \otimes G_{\left\lfloor\frac{n+1}{2}\right\rfloor} \right)^2 \textcircled{z} H}, {n \geq 3}

Bài tập: chứng minh rằng, với mọi {n \geq 1}, {G_n} là một {(d^{8n}, d^2, \alpha_n)}-spectral expander trong đó {\alpha_n = \alpha + O(\alpha^2)}; và nếu cho trước một đỉnh của {G_n} thì ta có thể tính được các đỉnh kề với nó trong thời gian {\text{poly}(n) = \text{poly}(\log(|V(G_n)|))}.

Chủ đề : Lý thuyết tính toán, Thuật Toán and tagged , , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

2 Comments

  1. roro
    Posted 18/03/2010 at 9:43 am | Permalink

    Anh Hưng sao không viết tiếp chuỗi bài PCP và Hardness of approximation này ạ? Em đọc đang hứng thú đến đây thì khựng 🙂

  2. Posted 18/03/2010 at 2:38 pm | Permalink

    @Roro: chờ tớ du hí về đã nhé.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*