Blog Khoa Học Máy Tính

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 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ư 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ỏ: . Cái dở là ta không thể “nhân” với 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 và là -spectral expander và -spectral expander, theo thứ tự. Chúng ta sẽ xây dựng một đồ thị mới, ký hiệu là , gọi là “tích zig-zag” của và . Tích này sẽ là một -spectral expander, trong đó cái spectral expansion rate mới nếu và . Nôm na là, nếu và là expanders thì cũng là expander.

Ta sẽ chứng minh được rằng (đây là chặn trên cụ thể, còn vẫn suy ra 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ị là -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:

Dễ thấy rằng đây là một chuỗi vô hạn các expanders. Đồ thị là một -spectral expander. Có thể cải tiến cái chặn trên đượ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ả . Chú ý rằng degree của bằng tổng số đỉnh của . Trước hết, với mỗi đỉnh của , đặt tên các cạnh xung quanh bằng các đỉnh của một cách tùy hỉ. Xem hình dưới đây, tôi đã đặt tên các cạnh xung quanh .

Mỗi đỉnh của là một cặp đỉnh . Có thể hình dung tập đỉnh của được chia thành “đám mây”, mỗi đám mây là một nhân bản của (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ì ở có cạnh với tên ở đầu là và tên ở đầu là , ta nối đỉnh trong đám mây của với đỉnh trong đám mây của 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à . 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 cạnh song song cho mỗi cạnh của ; ví dụ như sẽ có cạnh song song giữa đỉnh trong đám mây của và đỉnh trong đám mây của . Kết quả là một đồ thị với degree , 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 . Nếu ta có thể đi từ một đỉnh của đến một đỉnh của bằng cách thăm cạnh: xanh-đen-xanh, thì ta nối với thành một cạnh của . (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 . 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 bao gồm một bước ngẫu nhiên màu xanh trong một “đám mây” , một bước xác định (deterministic) qua một cạnh đen của , và một bước ngẫu nhiên (màu xanh) khác trong đám mây bên kia của . 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 là một cặp đỉnh , với là một đỉnh của và là một đỉnh của . Đỉnh 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 (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 gần uniform hơn vì 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 sẽ không làm giảm độ uniform của phân bố của . Còn nếu phân bố của đã là uniform thì bước một bước vẫn giữ nó uniform, trong khi đó phân bố của 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 . Tuy nhiên, vì các cạnh đen thực sự là một matching của các đỉnh của , do đó nếu ta tăng entropy của (phân bố của) thì sẽ làm giảm entropy của . Do đó, ta cần bước màu xanh thứ để tăng lại entropy của . (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 , đặt tên các cạnh kề với theo thứ tự tùy ý là . Đồ thị được xây dựng như sau:

• .
• Có một cạnh nối với nếu và chỉ nếu tồn tại sao cho , , và .

Dễ thấy rằng có đỉnh và (regular) degree . Gọi là các normalized adjacency matrices của , theo thứ tự. Định nghĩa một ma trận đặt tên là như sau: nếu và chỉ nếu . Lưu ý rằng là một ma trận hoán vị đối xứng (symmetric permutation matrix). Định nghĩa ma trận (trong đó là ký hiệu của tensor product của hai ma trận).

Bài tập: chứng minh rằng chính là normalized adjacency matrix của tích zig-zag .

Từ đó, ta có

Xét một vector tùy ý. Định nghĩa một “vector thu thập” như sau: . Nói cách khác, tọa độ thứ của là giá trị trung bình của các tọa độ trong “đám mây” thứ của vector . Đến đây, định nghĩa các thành phần song song và vuông góc:

trong đó là vector mà tất cả các tọa độ đều bằng ; và,

Xét vector , chúng ta muốn chứng minh rằng . Hãy bắt đầu với vế trái trước. Lưu ý rằng, do “phân bố đều” trên mỗi “đám mây”, ta có . (Bài tập: chứng minh điều này.)

Xét số hạng cuối cùng. Do vector “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 trên từng đám mây là bằng ), ta suy ra rằng .

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

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

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

Vì thế,

Lưu ý rằng . Ta suy ra

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

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

Nếu là một -spectral expander và là một -spectral expander thì tích zig-zag là một -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ị là . 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 là một -regular graph với đỉnh, là -regular graph với đỉnh. Tích tensor được định nghĩa như sau: , và hai đỉnh và là kề nhau nếu và chỉ nếu và .

Bài tập: chứng minh rằng nếu và là -spectral expander và -spectral expander, theo thứ tự, thì là -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 là một -spectral expander với các hằng số nào đó. Sau đó, định nghĩa

• 
• 
• ,

Bài tập: chứng minh rằng, với mọi , là một -spectral expander trong đó ; và nếu cho trước một đỉnh của thì ta có thể tính được các đỉnh kề với nó trong thời gian .

Chủ đề: Lý thuyết tính toán & Thuật Toán | Bình luận (2) »