Monthly Archives: May 2009

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

Ngô Quang Hưng | 31/05/2009 | Bản để in Bản để in
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ố , một chuỗi các đồ thị là một họ của các spectral expanders nếu là -spectral expander. Trong đó, , và tồn tại một đa thức sao cho với mọi . Điều kiện cuối [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | Phản hồi »

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

Ngô Quang Hưng | 29/05/2009 | Bản để in Bản để in
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 [...]
Chủ đề Lý thuyết tính toán, Thuật Toán, Xác suất & thống kê | 1 phản hồi »

Bô xít

Ngô Quang Hưng | 29/05/2009 | Bản để in Bản để in
Đại dự án bô-xít Tây Nguyên và ý kiến nhiều chiều (Tổng hợp các bài trên Vietnamnet) Vũ Ngọc Tiến, Tây Nguyên Du Ký (Diễn Đàn, 07/06/2009). Bài viết thú vị, nhưng hơi “văn vẻ” quá. Another Deal Blown, Where Will China Invest Now? (Time, 06/06/2009) Nguyễn Manh Hùng, Khai thác bô-xít Tây Nguyên: cái [...]
Chủ đề Tin tức đó đây | 18 phản hồi »

“A Cay” là bệnh tâm lý

Ngô Quang Hưng | 28/05/2009 | Bản để in Bản để in
Theo slashdot, trích một bài của LA Times: Some psychiatrists are trying to get excessive bitterness identified as a mental illness named post-traumatic embitterment disorder. Of course this has some people who live perfect little lives, and always get what they want, questioning the new classification. The so called “disorder” is modeled after post-traumatic stress [...]
Chủ đề Vui - Giải Trí | Phản hồi »

Phát biểu của ông Dương Trung Quốc

Ngô Quang Hưng | 27/05/2009 | Bản để in Bản để in
Chủ đề Tin tức đó đây | 19 phản hồi »

Cái gì đây kỳ này

Ngô Quang Hưng | 27/05/2009 | Bản để in Bản để in
Định bỏ post này vào mục “Vui — Giải Trí”, nhưng lại thôi. Trích bài báo của Tuổi Trẻ: Gần 20 năm đi biển hành nghề câu mực, anh Bổn – một trong 26 ngư dân thoát nạn – cho rằng: “Đi biển mà nhất là đi câu mực khơi xa chỉ sợ nhất là [...]
Chủ đề Tin tức đó đây | 2 phản hồi »

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

Ngô Quang Hưng | 22/05/2009 | Bản để in Bản để in
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 [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | 2 phản hồi »

Parallel parking

Ngô Quang Hưng | 21/05/2009 | Bản để in Bản để in
Mua xe này đi thi bằng lái À, nhưng nghĩ lại thì đàn xịn cách mấy mà gảy tai trâu thì cũng bằng thừa.
Chủ đề Vui - Giải Trí | 1 phản hồi »

Đo trình độ dân trí bằng Yahoo

Ngô Quang Hưng | 21/05/2009 | Bản để in Bản để in
Trong trang Yahoo Việt: http://vn.yahoo.com thì 360+ là đứng đầu menu, Chiêm Tinh là mục thứ 2, thứ 3 là Games, thứ 4 là Nhóm. Bên Anh http://uk.yahoo.com thì các mục menu là “Hỏi đáp, Ô tô, Hẹn hò, Tài chính” theo thứ tự Bên Pháp http://fr.yahoo.com thì là “Thời sư, Ô tô, Phim, Tài [...]
Chủ đề Vui - Giải Trí | 4 phản hồi »

On a related note

Ngô Quang Hưng | 20/05/2009 | Bản để in Bản để in
Tin nóng hổi về giải Godel năm nay: về tay Omer Reingold, Salil Vadhan, và Avi Wigderson do các bài báo xây dựng expander (zig-zag product mà chúng ta sẽ viếng thăm trong loạt bài PCP), và kết quả L=SL đã đề cập.
Chủ đề Tin tức đó đây | Phản hồi »

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

Ngô Quang Hưng | 20/05/2009 | Bản để in Bản để in
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 [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | 9 phản hồi »

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

Ngô Quang Hưng | 19/05/2009 | Bản để in Bản để in
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 [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | 10 phản hồi »

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

Ngô Quang Hưng | 18/05/2009 | Bản để in Bản để in
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ư [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | 11 phản hồi »

Giao trứng cho ác

Ngô Quang Hưng | 18/05/2009 | Bản để in Bản để in
Cập nhật 18 tháng 5: Cuối cùng thì có vẻ như các tin tức về chủ quyền trên server đã được/bị hủy bỏ. Ví dụ như http://211.88.5.96/cvweb/vcc/info/Article.jsp?a_no=180804&col_no=550 không còn chứa các tuyên bố chủ quyền này nọ nữa. Chắc là domain name www.vietnamchina.gov.vn sẽ được hồi phục nay mai. Còn thiếu mỗi việc … quy [...]
Chủ đề Mạng máy tính, Tin tức đó đây, Ảnh hưởng của CNTT | 1 phản hồi »

PCP 2 — ĐL PCP và NP-hardness của Gap-Max-E3SAT

Ngô Quang Hưng | 16/05/2009 | Bản để in Bản để in
5. Các thuật toán xấp xỉ cho các bài toán NP-Hard Một trong các cách để giải quyết một bài toán tối ưu nhưng lại bị NP-hard là thiết kế một thuật toán xấp xỉ cho nó. Đối với các bài toán này, có một trade-off về mặt bản chất giữa chất lượng lời giải [...]
Chủ đề Lý thuyết tính toán, Thuật Toán | 13 phản hồi »