Category Archives: Lý thuyết tính toán

Lý thuyết độ phức tạp, độ phức tạp thuật toán, vân vân.

Giải thưởng Turing 2012

Giải thưởng Turing (được ví như giải Nobel của ngành Khoa học máy tính) lần này sẽ được trao cho Shafi Goldwasser và Silvio Micali. Các bạn có thể xem thông báo chính thức “Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography” tại đây. Hai đóng góp nổi bật của Goldwasser và Micali là […]

Cũng thuộc về chủ đề Bảo mật và mật mã học, Lý thuyết mã hóa | Tagged , , | 1 phản hồi »

Độ phức tạp của bài toán định trị truy vấn

Bài trước: Logic bậc nhất và truy vấn hội Bài sau: Thuật toán Yannakakis Bài trước lược khảo các khái niệm và kết quả của logic bậc nhất và định nghĩa truy vấn hội (conjunctive queries). Một cách vắn tắt, lớp các truy vấn hội là lớp các truy vấn có dạng trong đó là […]

Cũng thuộc về chủ đề Cơ sở dữ liệu, Logic | Tagged , , , | Phản hồi »

Polytime và polydata

Mấy hôm nay đọc một số bài viết về việc học mô hình hỗn hợp (mixture models). Đây là lĩnh vực kinh điển trong thống kê, nhưng vẫn tiếp tục là một lĩnh vực mở đang được quan tâm trong thống kê, học máy cũng như thuật toán. [Tôi cũng vừa upload bài mới trên […]

Cũng thuộc về chủ đề Lý thuyết thông tin, Thuật Toán, Toán Ứng Dụng, Xác suất & thống kê | Tagged , , , , | 7 phản hồi »

Mật mã khóa công khai: hành trình 35 năm

(Một phiên bản ngắn hơn của bài  này sẽ đăng trong số kỷ niệm 20 năm báo Tia Sáng. Các bạn có thể xem tại đây) Mã hóa khóa công khai ra đời cách đây 35 năm, đánh dấu bởi công trình khoa học của Whitfield Diffie và Martin Hellman. Đó thực sự là một […]

Cũng thuộc về chủ đề Ảnh hưởng của CNTT, Bảo mật và mật mã học, Toán Ứng Dụng | Tagged , , , , , , | 20 phản hồi »

HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

HM4: Độ phức tạp mẫu và VC dimension. HM6: Độ phức tạp Rademacher Hai mô hình (nhất quán và PAC) chúng ta thấy cho đến nay đều không thực tế lắm. Trên thực tế dữ liệu thường có nhiễu, việc tìm một giả thuyết nhất quán với nhiều mẫu trở nên khó khăn. Đôi khi […]

Cũng thuộc về chủ đề Trí tuệ nhân tạo, Xác suất & thống kê | Tagged , , | 12 phản hồi »

Trả lời nhanh vài câu hỏi về phân tích thuật toán

Bạn Thắng có vài câu hỏi về phân tích độ phức tạp thuật toán, tôi trả lời vắn tắt dưới đây.

Cũng thuộc về chủ đề Thuật Toán | Tagged , , , , | 11 phản hồi »

PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

Trong bài này chúng ta giới thiệu biến đổi Fourier trên các nhóm Abel hữu hạn, giải tích Fourier của các hàm Bool, và giới thiệu lý thuyết bầu cử cùng với chứng minh định lý Arrow về tính duy lý của sự độc tài.

Cũng thuộc về chủ đề KHMT và Kinh Tế, Thuật Toán, Xác suất & thống kê | Tagged , , , , , | 15 phản hồi »

Mật mã dưới góc nhìn độ phức tạp tính toán

Bài này thảo luận mối liên hệ mất thiết giữa lý thuyết mật mã và lý thuyết độ phức tạp tính toán.

Cũng thuộc về chủ đề Bảo mật và mật mã học | 16 phản hồi »

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 […]

Cũng thuộc về chủ đề Thuật Toán | Tagged , , , , | 2 phản hồi »

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

Trong bài này ta thảo luận các phép xây dựng đồ thị expander, và một vài ứng dụng của chúng: tiết kiệm bit ngẫu nhiên và khuếch đại gap.

Cũng thuộc về chủ đề Thuật Toán | Tagged , , , | Phản hồi »

PCP 7 — Expanders: góc nhìn xác suất

8.d. Spectral expanders và tốc độ hội tụ của random walks trên expanders Trong bài này chúng ta sẽ chứng minh rằng một đồ thị có spectral gap lớn thì “tương đương” với tốc độ hội tụ của một random walk trên đồ thị càng cao. (Sở dĩ ta để tương đương trong ngoặc kép […]

Cũng thuộc về chủ đề Thuật Toán, Xác suất & thống kê | Tagged , , | 1 phản hồi »

PCP 6 — Expanders: góc nhìn đại số

8.c. Algebraic graph theory và spectral expansion Để định nghĩa expanders từ góc nhìn đại số, ta cần biết một chút về algebraic graph theory và đại số tuyến tính. Về AGT thì tôi giới thiệu 2 quyển sau đây: Algebraic Graph Theory của Biggs, Spectral Graph Theory của Fan Chung. Về đại số tuyến […]

Cũng thuộc về chủ đề Thuật Toán | Tagged , , , | 2 phản hồi »

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

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 […]

Cũng thuộc về chủ đề Thuật Toán | Tagged , , , | 9 phản hồi »

PCP 4 — Gap-preserving reduction và bài toán LabelCover

7.d. Vài ví dụ về gap-preserving reduction Những reduction tầm thường như kiểu từ Gap-Max-Clique về Gap-Max-IndependentSet sẽ có tính chất gap-preserving một cách hiển nhiên. Chúng ta xét vài ví dụ không tầm thường: Gap-Max-3SAT(d), Gap-Max-E3SAT(Ed) và Gap-Max-LabelCover; sau này sẽ dùng chúng để chứng minh định lý Hastad và làm động cơ giới […]

Cũng thuộc về chủ đề Thuật Toán | 10 phản hồi »

PCP 3 — Khó xấp xỉ, gap-producing reductions, FGLSS reduction

7. Cơ bản về chứng minh sự khó xấp xỉ Trong bài trước, chúng ta đã chứng minh rằng định lý PCP tương đương với Gap-Max-E3SAT là NP-Hard với một hằng số nào đó. Chúng ta sẽ thấy rằng định lý PCP cũng tương đương với một số gap-problems khác là NP-Hard, ví dụ như […]

Cũng thuộc về chủ đề Thuật Toán | 11 phản hồi »