PCP 5 — Expanders: định nghĩa và góc nhìn tổ hợp

NQH | 20/05/2009 |

8. Expanding graphs, còn gọi là expanders

Hôm nay chúng ta “de-tour” một chút để nói về expanders. Đã dùng một loại expander đặc biệt trong bài trước. Bây giờ cần giới thiệu kỹ hơn để dùng vào nhiều việc sau. Chắc sẽ cần ít nhất 3 bài để nói về expanders. Bài survey của S. Hoory, N. Linial , A. Wigderson trên Bulletin of the AMS là tham khảo chính trong KHMT về expanders. Bài này được giải Levi L. Conant 2008 cho exposition tốt. Có vẻ như họ đang viết một quyển sách về expander.

8.a. Trực quan

Expanders là một họ các đồ thị hữu dụng vô cùng tận trong KHMT hiện đại. Có thể nói là nhìn đâu cũng thấy expanders. Nó là cái gì ghê vậy? Về mặt trực quan, có ba cách tương đương nhau để mô tả expanders.

Góc nhìn tổ hợp (combinatorial view). Một expander là một đồ thị thưa nhưng lại liên thông mạnh (sparse yet highly connected). Thường thì ta giới hạn max-degree là hằng số để lượng hóa khái niệm “thưa”. Còn “liên thông mạnh” thì đo bằng số cạnh hoặc đỉnh cần loại bỏ để cắt liên thông (disconnect) đồ thị. Nói cách khác, một expander là một đồ thị có max-degree bị chặn; và, bất kỳ một tập “nhỏ” các đỉnh nào cũng có neighborhood “lớn” (có biên giới lớn).
Khi nhìn expander theo cách này chúng ta sẽ thấy nó nhiều ứng dụng rất tự nhiên: dùng nó để nối mạng P2P (hoặc để phân tích connectivity), để thiết kế worm propagation schemes hoặc thiết kế botnet command propagation, để thiết kế topology cho switching networks (xem bài này về WDM network, hay bài này về telephone switching networks), để chứng minh hardness of approximation như ta đã làm trong bài trước, để xây dựng error-correcting codes, vân vân.
Góc nhìn xác suất (probabilistic view). Một expander là một đồ thị mà nếu ta bước ngẫu nhiên dọc theo các cạnh (take a random walk on it) thì ta sẽ tiến đến cái stationary distribution rất nhanh (rapidly mixing walks).
Khi nhìn expander theo cách này, cũng có nhiều ứng dụng tự nhiên. Ta dùng nó để thiết kế cryptographic hash function, tiết kiệm tổng số random bits cho một thuật toán ngẫu nhiên hóa, để khuếch đại gap giữa soundness và completeness, để de-randomize, để sampling hiệu quả, để chứng minh complexity results (như kết quả lừng danh gần đây L=SL của Omer Reigngold), để chứng minh định lý PCP (theo cách của Dinur như đã nói), vân vân. Dĩ nhiên, các ứng dụng đều phần nào chuyển qua chuyển lại giữa hai góc nhìn tổ hợp và xác suất. Cho nên, phân loại ứng dụng của expanders theo góc nhìn là hơi khiên cưỡng một chút.
Góc nhìn đại số (algebraic view). Một họ expanders là một họ đồ thị mà khoảng cách giữa eigenvalue lớn nhất và lớn nhì bị chặn dưới bởi một hằng số. Cái khoảng cách này còn được gọi là spectral gap của họ đồ thị này. Đại khái, spectral gap càng lớn thì tốc độ mở rộng (expand) càng lớn, tốc độ hội tụ về equilibrium của random walk càng lớn. Góc nhìn đại số cũng có các ứng dụng riêng, nhưng ứng dụng quan trọng nhất đối với chúng ta là dùng để phân tích các expanders theo hai góc nhìn kia. Ví dụ: việc xác định expansion rate của một đồ thị là NP-hard, cho nên cái expansion rate do phương pháp đại số cung cấp, dù yếu hơn expansion rate thật sự, lại rất quan trọng trong các ứng dụng.

8.b. Combinatorial expansion và sự tồn tại của các expanders

Trước hết, hãy định nghĩa expanders từ góc nhìn tổ hợp. Cho một đồ thị $G=(V,E)$ (có thể có multi-edges). Với một tập con $S\subset V$ bất kỳ, ta dùng $\partial S$ để ký hiệu tập tất cả các cạnh “đâm ra” từ $S$ (nghĩa là nối $S$ với $V-S$ ), và $\Gamma(S)$ để ký hiệu tập các đỉnh kề với ít nhất một đỉnh của $S$ . Chú ý rằng $\Gamma(S)$ có thể giao với $S$ .

Định nghĩa. (Isoperimetric numbers và edge/vertex expanders)

Đại lượng $\displaystyle h(G) = \min_{|S| \leq n/2} \frac{|\partial S|}{|S|}$ được gọi là edge-isoperimetric number của $G$ . (Đây là phiên bản rời rạc của hằng số Cheeger trong hình học Riemann.)

Đại lượng $\displaystyle g(G) = \min_{|S| \leq n/2} \frac{|\Gamma(S) \setminus S|}{|S|}$ được gọi là vertex-isoperimetric number của $G$ .

Một $(n,d,c)$ -edge expander là một đồ thị $d$ -regular, có $n$ đỉnh, và $h(G) \geq c$ .

Một $(n,d,c)$ -vertex expander là một đồ thị $d$ -regular, có $n$ đỉnh, và $g(G) \geq c$ .

Khi nghĩ về expanders, ta nên nghĩ đến $n$ lớn, còn $c,d$ là các hằng số. Con số $c$ thường được gọi là expansion rate của đồ thị. Hai bài tập sau cho thấy hai khái niệm edge-expansion và vertex-expansion là tương đương.

Bài tập. Chứng minh rằng nếu $G$ là một $(n,d,c)$ -edge expander, trong đó $c,d$ là các hằng số, thì $G$ cũng là một $(n,d,c')$ -vertex expander với một hằng số $c'$ nào đó.

Bài tập. Chứng minh rằng nếu $G$ là một $(n,d,c)$ -vertex expander, trong đó $c,d$ là các hằng số, thì $G$ cũng là một $(n,d,c')$ -edge expander với một hằng số $c'$ nào đó.

Bài tập. Chứng minh rằng nếu $G$ là một $(n,d,c)$ -vertex expander trong đó $c$ là một hằng số thì đường kính của đồ thị là $O(\log n)$ . Chú ý rằng một đồ thị với $n$ đỉnh phải có đường kính $\Omega(\log n)$ . Do đó expanders có đường kính tối ưu (trong vòng một tỉ lệ hằng số).

Bài tập. Cho một $(n,5,5)$ -expander, ít nhất phải “cắt” đi bao nhiêu cạnh để disconnect đồ thị?

Do hai khái niêm edge/vertex expanders gần như tương đương, hãy chỉ xét edge-expanders. Trước hết, câu hỏi tự nhiên nhất là với bộ tham số $(n,d,c)$ như thế nào thì một $(n,d,c)$ -edge expander tồn tại? Phương pháp xác suất cho ta câu trả lời. Đó là liên kết đến bộ bài giảng của tôi về PPXS. Nếu các bạn muốn đọc sách về PPXS thì tôi giới thiệu 3 quyển, từ dễ đến khó:

Đại khái, Bella Bolobas trong bài này và Noga Alon trong bài này cho ta biết rằng:

Định lý.

Khi $n$ đủ lớn, nếu ta chọn ngẫu nhiên một đồ thị $d$ -regular, với $d \geq 3$ , thì với xác suất cao edge-isoperimetric number sẽ lớn hơn $d/2 - \sqrt{d\log 2}$ . Ngoài ra, tồn tại một hằng số $c_2$ sao cho mọi đồ thị $d$ -regular đều có edge-isoperimetric number bị chặn trên bởi $d/2-c_2\sqrt d$ . Do đó, có thể nói là expansion rate tốt nhất cho một $d$ -regular graph là $d/2 - \Theta(\sqrt d)$ .

Với các giá trị $d$ nhỏ thì ta có các kết quả cụ thể hơn nữa. Bollobas chứng minh được, với mọi $n$ đủ lớn, tồn tại

$(n,3, 2/11)$ -edge expanders
$(n,4, 11/25)$ -edge expanders
$(n,5, 18/25)$ -edge expanders
$(n,6, 26/25)$ -edge expanders
$(n,9, 2.06)$ -edge expanders

Bài tập. Cho một $d$ -regular graph $G$ bất kỳ, chọn ngẫu nhiên một tâp $S$ các đỉnh với $|S|=\lfloor n/2 \rfloor$ . Chứng minh rằng

$\displaystyle \mathbb E\bigl[ |\partial S| \bigr] = \frac{\frac{dn}{2}\lfloor n/2 \rfloor \lceil n/2 \rceil}{\binom n 2}$
Từ đó, kết luận rằng với $n$ lớn thì expansion rate của $G$ không thể tốt hơn $d/2$ . Đây là kết quả yếu hơn kết quả trong định lý, nhưng bài tập này minh họa trực quan tại sao expansion rate không thể tốt hơn $d/2-o(d)$ .

Bài tập. Chứng minh rằng, với bất kỳ $c>0$ nào thì không tồn tại một họ vô hạn các $(n,2,c)$ -edge expanders. (Do đó, điều kiện $d \geq 3$ ở định lý trên là cần thiết nếu ta muốn expansion rate lớn hơn một hằng số.)

Mặc dù có thể chứng minh là tuyệt đại đa số các regular graphs là expanders, việc xây dựng một họ expanders trong poly-time thật sự là vấn đề cực kỳ nan giải. Cái khó nhất là tìm một chặn cho expansion rate cho của các đồ thị mà chúng ta xây dựng. Trong nhiều ứng dụng, điều chúng ta cần là một họ vô hạn các expanders với expansion rate lớn hơn một hằng số nào đó. Sẽ nói về vài phép xây dựng expanders trong bài tới.

Định lý trên cho ta biết rằng với mọi $d\geq 3$ , tồn tại vô hạn các $(n,d,c)$ -expander với expansion rate $c$ cỡ khoảng $d/2-\Theta(\sqrt d)$ . Thử đặt câu hỏi ngược lại: cho trước một expansion rate $c>0$ nào đó, có tồn tại một số vô hạn các $(n,d,c)$ -edge expanders với $d$ là một hằng số nào đó không? Câu trả lời dĩ nhiên là CÓ. Ví dụ, chọn $d$ để cho $d/2 - \Theta(\sqrt d) = c$ và áp dụng định lý trên là xong.

Tuy nhiên, chúng ta sẽ trả lời trực tiếp câu hỏi trên, không cần Bollobas và Alon giúp, bằng cách chứng minh định lý sau đây. Kết quả của Bollobas ở trên cũng dùng kỹ thuật tương tự. Tôi chọn định lý này và trình bày chứng minh của nó vì đây là một bài tập tôi thiết kế cho lớp randomized algorithms and probabilistic analysis. Chắc bạn sẽ không tìm được chứng minh này ở chỗ khác. Chứng minh này là minh họa tốt cho kỹ thuật dùng union bound và ép các tổng binomials trong phương pháp xác suất.

Định lý. (Nôm na: tồn tại vô hạn các $(n,d,c)$ -expanders với $c$ cho trước tùy ý và $d$ là hằng số phụ thuộc vào $c$ ).

Với mọi $c>0$ , tồn tại một hằng số $d_0>0$ thỏa điều kiện sau đây: với mọi $d \geq d_0$ , tồn tại $n_0>0$ sao cho một $(n,d,c)$ -edge expander tồn tại với mọi $n\geq n_0$ .

Chứng minh. Không mất tính tổng quát, ta có thể giả sử $c \geq 1$ , tại vì một $(n,d,1)$ -expander cũng là một $(n,d,c)$ -expander với mọi $c<1$ .

Ý tưởng của phương pháp xác suất là chọn một đồ thị $d$ -regular ngẫu nhiên. Chứng minh rằng nó là $(n,d,c)$ -edge expander với xác suất dương, nếu $n,d$ đủ lớn. Xong! Hai vấn đề cần giải quyết là: (a) chọn đồ thị $d$ -regular ngẫu nhiên như thế nào, và (b) làm thế nào để chặn xác suất nó là expander.

(a) Để chọn đồ thị $d$ -regular ngẫu nhiên, ta dùng cái gọi là configuration model của Bollobas. (Xem bài survey này về các models cho random regular graphs.) Không mất tính tổng quát, ta giả sử $n,d$ đủ lớn và $nd$ là số chẵn. Như thế nào là đủ lớn thì sẽ chỉ định sau. Việc bớt một đỉnh khỏi một expander có ảnh hưởng rất ít đến expansion rate của nó. Do đó, giả định $nd$ là chẵn không ảnh hưởng đến tính chính xác của chứng minh.

Trong configuration model, đầu tiên ta có một tập $V$ gồm $n$ đỉnh. “Chẻ” mỗi đỉnh $v \in V$ thành $d$ đỉnh con $v_1,\dots,v_d$ . Gọi tập các đỉnh con này là tập $U$ . Thì, $|U| = dn$ . Bây giờ, chọn một perfect matching trên $U$ . (Nói cách khác, ghép cặp ngẫu nhiên các đỉnh của $U$ thành $dn/2$ cặp.) Rồi gom các đỉnh con lại thành đỉnh lớn trong $V$ như cũ. Chúng ta được một đồ thị $G$ $d$ -regular. Xem hình dưới đây với $n=4, d=3$ . Đồ thị $G$ có thể có loop và multi-edges, và điều đó không ảnh hưởng gì.

(b) Ta sẽ chứng minh $G$ không là $(n,d,c)$ -expander với xác suất nhỏ hơn $1$ rất nhiều. Dó đó, đa số các $d$ -regular graphs là $(n,d,c)$ -expanders.

Nếu $G$ không phải là $(n,d,c)$ -expander, thì phải tồn tại một tập con $S\subseteq V$ với kích thước $|S|=s \leq n/2$ sao cho $|\partial S| < c|S|$ . Ở trong $S$ có tất cả $ds$ đỉnh "con". Gọi $S'$ là tập các đỉnh con. Gọi $T$ là tập các đỉnh của $S'$ được bắt cặp lẫn nhau, trong nội bộ chúng nó. Suy ra, $|\partial S| = |S'|-|T|$ . Dĩ nhiên $|T| = 2t$ với $t$ là một số nguyên dương thỏa $s(d-c) < 2t \leq ds$ (Bài tập: tại sao?).

Cho một tập con $S\subset V$ với $|S|\leq n/2$ bất kỳ, và tập con $T \subseteq S'$ với $s(d-c) < 2t \leq ds$ bất kỳ, định nghĩa $A_{S,T}$ là sự kiện (probability event) mà các thành viên của $T$ được bắt cặp lẫn nhau, nội bộ. Để cho $G$ không là expander, sự kiện $A_{S,T}$ phải xảy ra với $S,T$ nào đó. Do đó, nhờ union bound, ta có

$\displaystyle \text{Prob}[ G \text{ is not an } (n,d,c)\text{-edge expander} ] \leq \text{Prob}\left[ \bigcup_{S,T}A_{S,T} \right] \leq \sum_{S,T} \text{Prob}\left[A_{S,T}\right]$

Tổng số perfect matchings trên $2k$ đỉnh là cái “giai thừa kép” $(2k-1)!!$ . Do đó, $\text{Prob}\left[A_{S,T}\right] = \frac{(2t-1)!! (nd-1-2t)!!}{(nd-1)!!}$ . Ta kết luận là xác suất mà $G$ không là expander được chặn trên bởi

$\displaystyle \sum_s \sum_t \binom n s \binom{ds}{2t} \frac{(2t-1)!! (nd-1-2t)!!}{(nd-1)!!} = \sum_s \sum_t \frac{\binom n s \binom{ds}{2t} \binom{dn/2}{t}}{\binom{dn}{2t}}$

Trong đó, ta lấy tổng theo các chỉ số $1 \leq s \leq n/2$ và $(d-c)s < 2t \leq ds$ .

Làm thế nào để chứng minh cái tổng khổng lồ này là nhỏ hơn $1$ ? Trước hết, đặt $a_t = \frac{\binom n s \binom{ds}{2t} \binom{dn/2}{t}}{\binom{dn}{2t}}$ cho tiện. Ta "bẻ gãy" cái tổng này thành 2 tổng nhỏ hơn:

$\displaystyle \sum_{s<\alpha n} \sum_t a_t + \sum_{\alpha n\leq s \leq n/2} \sum_t a_t = T_1+T_2$

Trong đó $0<\alpha < 1/2$ là một hằng số sẽ xác định sau. Kế đến, chú ý rằng nếu $d \geq 2c$ thì $a_t \geq a_{t+1}$ với mọi $t$ trong khoảng cho phép -- nghĩa là $(d-c)s/2 \leq t \leq ds/2$ . (Bài tập: chứng minh khẳng định này.)

Chúng ta chặn tổng $T_1$ trước. Chú ý là khi xét tổng này thì $\frac s n \leq \alpha$ . Dùng bất đẳng thức $\binom m k \leq \left(\frac{me}{k}\right)^k$ với mọi $m\geq k$ , ta chặn $a_t$ như sau:

$\displaystyle a_t = \binom n s \binom{dn/2}{t} \frac{ds(ds-1)\dots(ds-2t-1)}{dn(dn-1)\dots(dn-2t-1)} \leq \left(\frac{ne}{s}\right)^s \left(\frac{dne}{2t}\right)^{t} \left(\frac s n\right)^{2t}$

Do đó, với mọi $t$ , ta có

$\displaystyle a_t \leq a_{\frac{(d-c)s}{2}} \leq \left(\frac{ne}{s}\right)^s \left(\frac{dne}{(d-c)s}\right)^{\frac{(d-c)s}{2}} \left(\frac s n\right)^{(d-c)s}$

Chọn $d \geq c+6$ thì $\frac{d-c}{2}+1 \leq 2\left(\frac{d-c}{2}-1\right)$ . Sau khi sắp xếp lại các biến số, ta có:

$\displaystyle a_t \leq \left[ \left(\frac{ed}{d-c}\right)^{\frac{d-c}{2}+1} \times \left( \frac s n \right)^{\frac{d-c}{2}-1} \right]^s \leq \left[ \alpha \left( \frac{ed}{d-c} \right)^2 \right]^{\left(\frac{d-c}{2}-1\right)s}$

Tăng $d$ một chút để cho $d\geq 3c+6$ thì ta có $\frac{ed}{d-c} \leq \frac{3e}{2}$ và $\frac{d-c}{2}-1 \geq c$ . Đặt $\alpha = \frac{1}{36e^2}$ . Ta có thể chặn $a_t \leq (1/16)^{s(\frac{d-c}{2}-1)} \leq (1/16)^{cs}$ . Đến đây, chặn trên cái tổng thứ nhất:

$\displaystyle T_1 \leq \sum_{s=1}^{\alpha n} cs (1/16)^{cs} \leq \sum_{s=1}^\infty (1/8^c)^s = \frac{1/8^c}{1-1/8^c} \ll 1.$

Muốn làm chặn trên này nhỏ đến (hằng số) bao nhiêu cũng được, nhưng như vậy là đủ cho mục đích của ta. Kế đến, ta chặn cái tổng thứ hai $T_2$ . Lần này ta dùng một mẹo khác: dùng bất đẳng thức

$\displaystyle \frac{2^{mH_\beta}}{m+1} \leq \binom{m}{\beta m} \leq 2^{mH_\beta}$
trong đó, $H_\beta$ là hàm entropy nhị phân. ( $0<\beta < 1$ .) Để dùng mẹo này, đặt $\beta = s/n$ , $\delta=(d-c)/d$ . Chú ý rằng $\alpha \leq \beta = s/n \leq 1/2$ . Ta chặn từng term $a_t$ như sau:

$\displaystyle a_t \leq a_{\frac{(d-c)s}{2}} = \frac{\binom{n}{\beta n} \binom{ds}{(d-c)s}\binom{dn/2}{(d-c)s/2}}{\binom{dn}{(d-c)s}} \leq (dn+1)2^{nH_\beta + dsH_{\delta} + \frac{dn}{2}H_{\delta\beta} - dnH_{\delta\beta}}$

Khi ta chọn $d$ đủ lớn thì $\delta$ tiến gần đến $1$ và $H_\delta$ tiến gần đến $0$ . Do đó, có thể giả sử rằng $H_\delta \leq \frac 1 4 H_\alpha$ . (Chú ý rằng $\alpha$ là hằng số $1/36e^2$ đã chọn như trên.) Do đó, $dsH_\delta \leq \frac{dn}{8}H_\alpha$ . Còn khi $\delta$ đủ gần $1$ thì $H_{\delta\beta}$ đủ gần $H_\beta$ . Có thể giả sử rằng $H_{\delta\beta} \geq \frac 1 2 H_\beta$ . Như vậy ta đã chặn được

$\displaystyle a_t \leq (dn+1)\left(\frac 1 2\right)^{n\left( [\frac d 4 - 1]H_\beta - \frac d 8 H_\alpha \right)}$

Với $d \geq 10$ , số mũ của $1/2$ trong biểu thức trên sẽ ít nhất là một hằng số dương nhân với $n$ . (Chú ý rằng $H_\beta \geq H_\alpha$ .) Do đó, toàn bộ biểu thức là exponentially small. Như vậy, cái tổng $T_2$ cũng exponentially small (vì chỉ có polynomial number of terms). Do đó, với $n$ đủ lớn, tổng $T_2$ tiến đến $0$ .

QED

Bài tới chúng ta bàn về góc nhìn đại số của expanders. Bài sau đó là về góc nhìn xác suất.

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

9 Comments

Ngô Quang Hưng

Posted 21/05/2009 at 6:06 am | Permalink

Mới sửa lại vài typos. Hy vọng không còn lỗi nữa.

Reply
Thinh Nguyen

Posted 21/05/2009 at 6:40 am | Permalink

RC huynh hay có những suggestion rất theoritical giúp mở rộng, phát triển topic
Em thấy vấn đề “length-preserving witness” mà RC huynh raised trong phần comment của PCP4 cũng rất hay.

Reply
Thinh Nguyen

Posted 24/05/2009 at 7:32 pm | Permalink

Em tinh ra so perfect matching tren $2k$ dinh la: $k(k+1)\dots(2k-1)$

Cai preview plugin chay ngon anh a.

Reply
Thinh Nguyen

Posted 24/05/2009 at 8:05 pm | Permalink

Sorry, em nham

Reply
RongChoi

Posted 25/05/2009 at 1:51 pm | Permalink

Hi anh Hưng,
Cách xây dựng expander anh giới thiệu rất trực quan và phù hợp để chứng minh định lý về sự tồn tại vô hạn các expander. Nhưng có lẽ đây không phải là cách giải quyết cho một vấn đề trọng tâm khác là xây dựng hiệu quả các expander? Tính không hiệu quả của phương pháp này có thể thể hiện ở 2 chỗ:
- Với mỗi n, phải xây dựng lại Graph từ đầu chứ không tận dụng được những Graph có số đỉnh <n đã xây dựng. Với n lớn để có thể thực hiện hiệu quả Random walk trên nó thì n cỡ phải $2^{100}$ . Khi đó có lẽ phuơng pháp này khó khả thi. Có lẽ nên dùng phương pháp này để tìm ra một số Graph với số đỉnh cỡ vừa vừa, rồi sau đó áp dụng một số phương pháp để nhân rộng Graph? Nhưng nhân rộng số đỉnh mà vẫn giữ cố định bậc của các đỉnh chắc phải cần các kỹ thuật hay (dùng Tensor product đơn giản nhưng nhân rộng cả số đỉnh lẫn số bậc ).
- Phương pháp này cho ta Expander với xác suất gần 1 chứ không tuyệt đối. Không biết việc kiểm thử xem nó thực sự có là Expander có dễ dàng hay không? Áp dụng thẳng bằng cách tính trị đặc trưng thứ hai cho một graph cỡ $2^{100}$ đỉnh chắc hơi lâu. Không biết có thể có cách kiểm thử hiệu quả hơn cho họ Graph đặc biệt được xây dựng trong bài hay không? (họ Graph này có những đặc điểm giúp việc tính trị riêng được dễ dàng hơn?)

Anh Hưng sẽ có giới thiệu cách xây dựng Expander qua Zig-Zag product không?

PS: Cảm ơn anh Hưng đã cài preview plugin, nếu không lại đã có 1 post 1 dòng chữa 1 cái typo ^^

Reply
Ngô Quang Hưng

Posted 25/05/2009 at 2:54 pm | Permalink
Hello RongChoi, sẽ có bài về Zig-Zag. (Đặc biệt là sau giải Godel vừa rồi, không thể bỏ qua nó rồi.) Tôi có viết là kiểm tra expanding rate một cách chính xác thì NP-hard. Và nói chung, ngoài eigenvalue method ra thì tôi kô biết cách khác để verify expanders tổng quát. (Với các expanders đặc biệt — như xây dựng từ Cayley groups thì họa chăng có cách khác). Cái chứng minh xác suất trình bày ở trên có 3 điểm lợi:
- (1) là minh họa cho kỹ thuật union bound và ép binominal coefficients, có lẽ sẽ dùng về sau,
- (2) trong một số ứng dụng ta buộc phải dùng p.p. xác suất (ví dụ như P2P network, vậy mà kỳ infocom vừa rồi tôi vẫn review bài báo dùng zig-zag để construct p2p networks)
- (3) nó cho thấy chúng ta còn biết rất ít về expanders, vì tuyệt đại đa số các d-regular graphs là expanders mà chỉ biết có khoảng 3 cách khá convoluted để xây dựng chúng.
- (4) đúng như RongChoi nói, sẽ cần dùng expanders nhỏ (constant size, xây dựng bằng ppsx) để xây dựng các expanders có kích thước bất kỳ.
Reply
Thinh Nguyen

Posted 26/05/2009 at 4:33 am | Permalink

Hi anh Hưng, RC huynh,

Về probabilistic method, em mới chỉ biết định nghĩa và vài ví dụ đơn giản (thực chất là counting + Markov, Chebysev inequality), em chưa quen sử dụng phương pháp này.

Bài trên đọc đến đoạn tách đôi tổng “khổng lồ” là em stop rồi Không hiểu đến bài “Góc nhìn xác suất” thì sẽ thế nào

Thinh

Reply
RongChoi

Posted 29/05/2009 at 12:38 am | Permalink

Hi anh Hưng,
3 cách xây dựng các expanders anh nói là gì nhỉ? Cách thứ nhất hẳn là ppxs và như anh giải thích, cách này phù hợp cho các ứng dụng trong network. Cách thứ 2 liệu có phải là đầu tiên xây dựng các graph theo phương pháp đại số khi ta có thể chặn trên trị riêng thứ hai mà không cần tính chính xác (Cayley graphs, Gabber-Galil graphs…) rồi sau đó có thể nhân rộng (bằng zig-zag product chẳng hạn), cách này sẽ phù hợp cho nhiều ứng dụng mang tính lý thuyết như Derandomization…? Cách thứ 3 …?
Vì không chắc anh sẽ đề cập đến tất cả các phương pháp xây dựng (vì mục đích chính là chứng minh định lý PCP) nên RC hỏi để dễ tìm hiểu sâu hơi, bởi quả thực không ngờ là expanders lại có sưc mạnh khá là đặc biệt trong nhiều lĩnh vực khác nhau đến vậy.

Reply
Ngô Quang Hưng

Posted 29/05/2009 at 11:19 am | Permalink

Hi RongChoi, cách 1 là cách xây dựng của Margulis (hồi 72, 73); Gabber-Galil chỉ chứng minh một expansion rate cụ thể của Margulis graph thôi. Cách thứ hai là của Lubotzky-Phillips-Sarnak (hồi 88) xây dựng Ramanujan graphs. Ramanujan graphs là các đồ thị tối ưu về spectral gap (nhưng không tối ưu về expansion rate). Cách thứ 3 là Zig-Zag product (combinatorial construction), rất khác với các cách kia (đại số). Còn một số bài báo khác phân tích một số Cayley graphs, nhưng ứng dụng của chúng không universal như 3 constructions trên.

Reply

PCP 5 — Expanders: định nghĩa và góc nhìn tổ hợp

9 Comments

Post a Comment Cancel reply

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

Mạng

Não học

Toán học

Vật Lý