Blog Khoa Học Máy Tính

Tản mạn về cơ hội trong ngành Thống kê (và KHMT)

Nguyễn Xuân Long | 03 tháng 07, 2009 | Bản để in

Thị trường công việc cho faculty ở các trường ĐH ở Mỹ năm nay đã khép lại. Tôi đã may mắn tìm được một vị trí mà mình yêu thích, và đang hứng khởi chuẩn bị dọn đến đối diện nhà bác Hưng ở bên kia bờ hồ. Cũng giống như việc chuẩn bị apply vào grad schools để theo đuổi PhD, quá trình nộp hồ sơ, phỏng vấn và thăm viếng các trường ĐH là một rite of passage cho những ai đi theo con đuờng academia, và tất nhiên cũng để lại cho tôi nhiều ấn tượng đáng nhớ. Xin ghi chép lại đôi chuyện và một vài cảm nghĩ.

Mặc dù nộp đơn vào cả hai khoa Thống kê (TK) và KHMT, tôi thấy mình thích ở bên khoa Thống kê vì thấy văn hóa ngành này phù hợp vói temperament của mình. Về mặt nghiên cứu, nhất là lĩnh vực machine learning/ data mining thì ở bên KHMT hay bên TK sẽ không có khác biệt gì nhiều với những lĩnh vực quan tâm, và tôi đã và sẽ tiếp tục hợp tác với các đồng nghiệp ở cả hai khoa. Vì không làm PhD bên khoa TK nên lúc đầu tôi có nhiều e ngại về sự nhìn nhận của các khoa TK đối với mình. Thế giới academia về nhiều khía cạnh khá là bảo thủ và rất coi trọng truyền thống. Rất ít khi họ nhận người có PhD từ một khoa khác và ngành TK cũng không phải là ngoại lệ. (Đôi khi một PhD một ngành khác vẫn có thể có những vị trí joint appointment cho hai khoa (ví dụ 50% TK và 50% KHMT), tuy vậy những vị trí như vậy cũng rất hiếm hoi và cũng không mấy được ưa chuộng cho những người ở vị trí Assistant Professor vì lý do xét duyệt tenure phiền phức sau này. Phần lớn các joint appointment mà chúng ta thấy là dành cho senior faculty và là ở dạng courtesy mà thôi). Rất may tôi không cảm thấy có sự phân biệt nào đáng kể đối với trường hợp của mình. Ngoài cá nhân tôi, năm nay có một người nữa có background về machine learning cũng được nhận vào giảng dạy ở khoa TK Đại học Pennsylvania. Điều này nói lên sự cởi mở ngành TK tại thời điểm hiện nay, một giai đoạn chuyển dịch thú vị có thể ảnh hưởng lớn đến bộ mặt của các khoa TK và KHMT trong tương lai. Đây là một câu chuyện chính tôi muốn nói trong bài viết này.

Trong quá trình đi phỏng vấn, trò chuyện với nhiều người, tôi nhận thấy hai ngành KHMT và Thống kê có rất nhiều điểm tương đồng. Cả hai đều là ngành trẻ, dẫu có gốc rễ từ lâu nhưng thực sự cả hai chỉ bắt đầu cất cánh vào sau thế chiến 2. Ở Mỹ các khoa Thống kê bắt đầu được thành lập từ những năm 1950, 1960, thường tách ra từ khoa Toán. Các khoa KHMT cũng bắt đầu được thành lập từ những năm 1960’s, 1970’s, cũng tách từ khoa Toán hoặc Engineering. Sự ra đời của các khoa KHMT và TK có thể nói là một phần lớn do nhu cầu giải quyết các vấn đề thực tiễn phát sinh trong chiến tranh, công nghiệp, nông nghiệp và một số lĩnh vực trọng yếu khác. Khác với các ngành KH hay công nghệ khác thường có đối tượng nghiên cứu rất cụ thể (ví dụ, nuôi con nào trồng cây gì), đối tượng nghiên cứu của TK và KHMT mang tính khái quát khá cao (xoay quanh những vấn đề về inference và computation). Vì vậy TK và KHMT cũng có những vấn đề nghiên cứu nội tại khá sâu sắc và lý thú, mang đậm tính lý thuyết và triết lý. Với nhiều người đó có thể là lý do chính (hoặc ban đầu) thu hút họ đến với hai ngành này và bản thân tôi cũng đã bắt đầu như vậy. Nhưng như nói ở trên thì TK và KHMT phần lớn và về bản chất không phải là một ngành lý thuyết thuần túy. Chính tính ứng dụng cao của KHMT và TK, bằng cách tạo ra những công cụ cụ thể để có thể áp dụng trong các khoa học thực tiễn khác, là cái gốc rễ cung cấp động lực để hai ngành này tồn tại và phát triển. Vấn đề gì cần xử lý và phân tích dữ liệu thì cần phương pháp XSTK. Cần cấu trúc dữ liệu và giải thuật phức tạp thì cần công cụ KHMT. Thời đại ngày nay rất dễ thấy rất nhiều vấn đề trong mọi lĩnh vực đều cần cả hai thứ đó.

Công nghệ ngày nay cho phép chúng ta quan sát các hiện tượng tự nhiên, xã hội hay tính chất của các máy móc nhân tạo một cách rất tỷ mỷ bằng khả năng thu thập dữ liệu với số lượng rất lớn. Làm sao để “make sense” được núi dữ liệu khổng lồ này là một thử thách cần sự cộng tác của chuyên gia thống kê cũng như chuyên gia KHMT. Chính sự thay đổi vượt bậc về số luợng dữ liệu này đòi hỏi nhiều thay đổi căn bản trong phương pháp xử lý phân tích dữ liệu và các phưong pháp dự báo thống kê. Sự giao thoa giữa inferential efficiency và computational efficiency đang trở nên một vấn đề trung tâm của TK, và tôi tin rằng đây cũng là một vấn đề trung tâm (không chỉ trong machine learning mà cả) KHMT trong tương lai. Tôi đã từng viết ở Blog KHMT về quá trình giải quyết các vấn đề liên quan đến dữ liệu là sự tương tác: Data –> Models –>Algorithms. Theo truyền thống, anh làm TK sẽ tìm hiểu Data (nói chuyện với các chuyên gia về data đó), và xây dựng mô hình và phương pháp cách thức học/inference mô hình thích hợp. Có mô hình rồi, những vấn đề về data structure, thuật toán và implementation cụ thể đuợc đẩy cho anh làm KHMT. Khi data phức tạp, mô hình phức tạp, thuật toán cũng phức tạp theo, thì sự module hóa như vậy không khả thi /hiệu quả nữạ, cần phải có sự tradeoff giữa việc design mô hình và design thuật toán. Vì vậy cần phải có background về cả KHMT và XSTK mới có thể giải quyết vấn đề một cách hiệu quả. Rất có thể, trong tương lai, những khoa kiểu như khoa Machine Learning ở CMU sẽ được thành lập ở nhiều nơi, kết hợp va hấp thụ nhiều thứ đang được dạy/học riêng rẽ ở các khoa TK và KHMT. Khi ấy, bộ mặt khoa TK va KHMT cũng sẽ thay đổi và khác xa những gì chúng ta đang thấy ngày nay.

Trong khi KHMT đã trở nên khá quen thuộc với các thế hệ sinh viên VN gần đây, sự hiện diện của TK còn rất ít ỏi. Trong quá trình phỏng vấn ở 10 trường (có thể coi là trong top 20 ở Mỹ) tôi được dịp làm quen với vài bạn VN ở khoa TK. Một bạn ở Wisconsin-Madison và một bạn ở Florida. Một có background về analysis/PDE, một có background về probability truớc khi sang Mỹ theo đuổi PhD về statistics. Cả hai đều được các GS ở khoa đánh giá rất cao. Nếu tôi đi phỏng vấn ở các khoa KHMT, chắc sẽ có hân hạnh được gặp các SV VN nhiều hơn. Quả thực hiện nay còn quá ít SV người Việt học TK, so với ngành KHMT cũng như các ngành Engineering khác. Trong khi KHMT nghe cool với SV Việt nam, TK có lẽ không (chưa) có gì là cool lắm. Lực lượng giảng dạy và nghiên cứu TK ở Vietnam hình như rất ít ỏi, có lẽ chỉ đếm trên đầu ngón tay. Không rõ đã có trường nào có khoa thống kê riêng chưa. Tôi chắc là một đội ngũ có chuyên môn bài bản về mô hình, xử lý và phân tích dữ liệu có lẽ rất ít. Tôi có cảm giác sự hiểu biết của giới sinh viên đại học ở VN về ngành TK và những cơ hội của XSTK rất hạn chế do thiếu thông tin.

Xin nói qua về triển vọng công việc của ngành TK ở Mỹ. Theo tôi biết từ các department chairs thì những ai tốt nghiệp PhD về TK đều xin việc rất dễ. Các ngành Engineering thì lúc up lúc down, tùy vào what’s hot and what’s not. Công nghệ thay đổi rất nhanh, do đó đoán trước cái gì nóng là rất khó. Nhưng bên Stats thì bao giờ cũng cần người làm cho các công ty consultant cho chính phủ, insurance, healthcare, survey industries, và các công ty về finance. Gần đây các công ty high-tech như Google, Yahoo cũng đều có nhu cầu tìm PhD Stats. Trong khi thị trường faculty job cho EECS có phần đình trệ trong vòng 5-10 năm trở lại đây, thì bên TK thì sau một chu kỳ trì trệ của thập niên 80-90 lại bắt đầu khởi sắc. Điều này theo tôi liên quan đến sự chuyển dịch của ngành TK sang hướng computation nhiều hơn, như đã nói ở trên, và sự về hưu của một lớp các GS kỳ cựu lấy bằng PhD những năm 60-70 (đây là lớp PhD đào tạo bài bản đầu tiên ở các khoa TK ở Mỹ). Năm nay tôi nộp hồ sơ đến 15 khoa TK và 9 khoa KHMT, bởi vì chỉ có từng đó vị trí opening cho vị trí tenure-track. Sự chênh lệch này đáng kể vì thông thường các khoa KHMT lớn hơn TK rất nhiều và theo lẽ đó cũng có nhiều opening hơn. Ở Berkeley năm nay chỉ tuyển thêm 1 người (khoa này cực lớn với hơn 80 faculty và 1500 sinh viên), trong khi đó khoa TK (với khoảng 20-30 faculty) cũng được tuyển thêm1 người. Khoa KHMT ĐH Wisconsin-Madison (bác An Hải) cũng không có opening cho đến phút cuối, cuối cùng năm nay cũng tuyển hai người. Khoa TK (nhỏ hơn khoa KHMT như thường lệ) ở Wisconsin cũng tuyển thêm hai người năm nay.

Hiện nay mức độ cạnh tranh về graduate admissions (PhD programs) cho các khoa TK có thể vẫn còn thấp hơn bên EECS nhiều. Ở Duke năm vừa rồi có khoảng 200 hồ sơ, nhận khoảng 10. Như thường lệ, các bạn Trung Quốc và Ấn Độ luôn luôn là những người nhanh nhạy nhất. Nhưng trong số 200 hồ sơ đó có khoảng > 100 hồ sơ là tù Trung Quốc. Một faculty ở Purdue cũng cho hay có khoảng 300 hồ sơ, thì nghe đâu hơn 200 là từ TQ. Đây là điểm các bạn SV Việt nam nên lưu ý. Các khoa ai cũng thích diversity, và nếu học sinh đến từ VN chẳng hạn chắc chắn sẽ có ưu thế. Nhiều vị GS gốc TQ còn nói với tôi là họ không thích nhận nhiều SV từ TQ như vậy. Như đã nói ở trên job demand luôn steady hoặc up nên triển vọng về tenure-track position opening bên TK do đó cũng rất tốt. Theo nhiều người nhìn nhận, trong vòng 10 năm tới prospects về academia bên TK sẽ vẫn tốt cho những người có thế mạnh về computation, algorithms (bên cạnh background tốt về modern statistics).

Vì vậy các bạn có background tốt về toán, KHMT, các ngành khoa học tính toán (computational sciences), các ngành công nghê ở bậc đại học, nên tham khảo tìm hiểu thêm ngành XSTK trong khi lựa chọn hướng đi của mình. Thú thực hồi học undergraduate tôi có học một vài courses về statistics, học cộng trừ nhân chia mấy cái mean và variance thấy không thú vị gì cho lắm. Ở mức độ ĐH thường người ta chỉ dạy các dạng reciple cookbooks về Statistics, rất lạc hậu và tẻ nhạt. Thấy giống như học calculus bên Toán hay học lập trình Pascal bên KHMT vậy. Đó không phải là bức tranh thực sự của XSTK. Ngành XSTK hiện đại đang trở thành ngôn ngữ và công cụ cho khoa học và công nghệ hiện đại giống như ngành toán học đối vơi vật lý vậy. Các vấn đề trong nghiên cứu về XSTK rất dồi dào và phù hợp cho các tính cách khác nhau: ai thích toán, hoặc thích thuật toán, hoặc thích mô phỏng thế giới, hoặc thích nghiên cứu của mình có ứng dụng trực tiếp đến cuộc sống đều có thể tìm được cho mình một mảng đề tài phù hợp. Nếu bạn từng được các ngành như trí tuệ nhân tạo, machine learning, signal processing, communication theory, information theory kích thích trì tò mò và say mê, thì rất có thể ngành Xác suất thống kê là ngành thích hợp cho khả năng và tính cách của mình.

Bài viết này có thể hơi self-center về ngành TK một chút. Xin được nói ngay là có rất nhiều ngành hay khác nhau và những cơ hội khác nhau cho tất cả mọi người. KHMT hay TK chỉ là một vài lựa chọn trong rất nhiều lựa chọn đó. Mong muốn của tôi ở đây chủ yếu là cung cấp thêm một số thông tin có thể sẽ hữu ích để tham khảo, đặc biệt những ai xuất thân từ KHMT, toán, hoặc các ngành kỹ thuật khác, đang loay hoay tìm kiếm một con đuờng đi tiếp cho nghiên cứu lâu dài cho mình. Hy vọng trong tương lai không xa sẽ có thêm đồng nghiệp VN, không chỉ trong KHMT mà cả trong XSTK nữa.

Chuyên mục: Dành cho du học sinh | Bình luận »

Đệ qui

Ngô Quang Hưng | 29 tháng 06, 2009 | Bản để in

Có một tác giả bị bảo vệ sân bay bắt và tra hỏi vì viết truyện tranh về một tác giả bị bảo vệ sân bay bắt và tra hỏi.
Gần đây thấy có mấy chỗ tranh luận về đề tài dân chủ cho ai. Bên Talawas chẳng hạn. Đại khái, sau vụ LCĐ có một bạn bên x-cafe viết rằng có khả năng đa số người VN, kể cả những người học hành đàng hoàng, không cần “dân chủ”. Như vậy, trước khi đấu tranh cho “dân chủ”, người ta cần nghiên cứu thị trường một cách … “dân chủ” xem là dân có cần cái “dân chủ” mà người đấu tranh vì “dân chủ” muốn đấu tranh cho hay không.
Trong phát biểu đệ qui trên, tôi bỏ qua câu hỏi “dân chủ là gì?” (Tôi thấy người ta hay dùng định nghĩa khác nhau cho cùng một chữ dân chủ trong các phần khác nhau của … cùng một câu. Ví dụ như trong câu trên, hay câu “bọn dân chủ không hiểu gì về dân chủ cả”.)
Câu hỏi “dân chủ là gì?” này rất quan trọng vì, không phải cái gì cũng giống như nước hoa, trước khi đem bán là phải nghiên cứu thị trường: “anh ngửi hộ iem cái”, “chị thích mùi này không?”
Nếu “dân chủ” giống nước hoa thì phải đi làm survey là đúng rồi.
Còn nếu “dân chủ” giống kháng chiến thì chắc là không cần. Sẽ phải dân vận, nhưng không cần làm survey.

Chuyên mục: Tin tức đó đây | Bình luận (2) »

Sài Gòn: Hằng và Biến

Lê Hoàng Long | 28 tháng 06, 2009 | Bản để in

Đã xa một thời gian, nay tôi mới có dịp về thăm Sài Gòn. Sài Gòn đổi thay nhanh quá, tôi như không nhận ra chính mình! Nhưng trong cái biến động đó, có những thứ mà so với hai ba năm trước vẫn không thay đổi.

Sài Gòn bây giờ kẹt xe nhiều hơn trước. Hôm đầu tiên đi ra đường để sang thăm gia đình vợ, cái nóng hầm hập bởi nắng Sài Gòn cùng với khói bụi và tiếng còi xe tác động mạnh vào các giác quan của tôi khiến lúc về nhà người tôi muốn lên cơn sốt. Ban đầu tôi nghĩ chỉ vì mình chọn ngay giờ cao điểm để đi ra đường, nhưng hóa ra đường Sài Gòn đông đúc và khói bụi không kể giờ giấc. Đường sá đã chật lại càng trở nên chật hơn với vô số công trình giao thông và xây dựng. Mật độ xe Sài Gòn tăng lên như vậy, nhưng người ta vẫn vô tư đi ngược chiều, vẫn vô tư vượt đèn đỏ, vẫn vô tư dừng xe lấn vạch, và những chiếc xe buýt sơn xanh vẫn vô tư lưu thông một cách trịch thượng. Sau bao năm rồi, cái còi xe vẫn chưa được dùng một cách lịch sự. Người ta nhấn còi để thúc giục người đang dừng đèn đỏ phía trước, dù cho đèn chỉ vừa chớm chuyển sang xanh, hay thậm chí khi vẫn còn đang đỏ. Người ta nhấn còi mà không cần biết tiếng còi xe của mình có giải quyết được ách tắc giao thông hay không, có khiến dòng xe đông đúc di chuyển nhanh hơn được chút nào hay không, có làm người khác khó chịu hay không. Nói cách khác, đối với nhiều người, ý thức văn hóa khi lưu thông trên đường vẫn không thay đổi, dù chiếc xe họ đang đi xịn hơn trước đây gấp nhiều lần.

Sài Gòn bây giờ quả là có nhiều xe xịn hơn trước, và người Sài Gòn ăn mặc đẹp hơn trước. Tôi hay đi với thằng em, được nó nhiều lần chỉ cho thấy những chiếc xe máy giá trị 150-200 triệu đồng mà hồi tôi rời Sài Gòn vẫn còn chưa xuất hiện. Rồi những chiếc xe hơi với giá trị tiền tỉ, thậm chí chục tỉ, lưu thông trên đường, điều mà trước đây hiếm hoi lắm tôi mới thấy được. Điều khiển những phương tiện lưu thông ấy là những người mặc đẹp và thời trang. Tôi đi trên đường thấy nhiều cửa hàng bán quần áo thời trang hơn trước. Và dĩ nhiên không chỉ cửa hàng quần áo, cửa hàng bán giày dép, điện thoại di động, điện máy, mỹ phẩm v.v… đền nhiều hơn trước. Đó là một sự biến đổi, phản ánh đời sống vật chất của dân Sài Gòn đã khá hơn hồi đó. Nhưng dù ăn mặc đẹp, điều khiển xe xịn, người ta vẫn thản nhiên vứt tàn thuốc lá, vẫn khạc nhổ trên đường. Tôi vẫn bị chen hàng khi xin hồ sơ cấp mới hộ chiếu, khi tính tiền trong siêu thị, hay khi mua vé xem phim. Xem phim xong, tôi vẫn thấy vỏ chai nước và hộp bắp rang bơ xả đầy các hàng ghế. Đầu con hẻm nhà tôi, không biết rác nhà ai cứ vô tư chất đống. Tôi vẫn nghe quá ít những câu “cảm ơn”, “xin lỗi”, “không có chi”. Bao lâu rồi, những điều ấy vẫn chưa được thay đổi.

Về được 1 bữa, tôi nhận ra rằng đi ăn hàng quán ở Sài Gòn bây giờ tốn kém hơn trước. Tôi hết hồn khi biết ổ bánh mì thịt tôi thường ăn trước đây giờ đã tăng giá gấp 3 lần. Quán phở trên đường Võ Thị Sáu giờ tăng giá gấp đôi, mà chất lượng thì giảm sút so với trước. Tiệm mì Tàu gần nhà vợ là địa điểm ăn sáng thường xuyên của tôi trước đây vì giá cả rất hợp túi tiền, giờ đây cũng tăng gấp rưỡi mà ăn xong, hai má tôi nhức tê vì bột ngọt. Mà không chỉ hàng quán mới tăng giá. Hầu như cái gì giá cũng tăng gấp đôi, gấp ba so với chỉ một hai năm về trước, dù có nhiều thứ Sài Gòn không hề khan hiếm. Giá cả thay đổi là vậy, nhưng tiền lương hưu của mẹ tôi vẫn không thay đổi. Mẹ tôi vẫn còn đi dạy hợp đồng, vẫn có khoản thu nhập thêm, nhưng còn nhiều thầy cô giáo khác phải chật vật sống với đồng lương ít ỏi. Tầng lớp thu nhập thấp ở Sài Gòn vẫn phải bươn chải, khổ sở trăm bề để mưu sinh, để tồn tại. Cho nên câu chuyện trong bữa cơm gia đình Sài Gòn bây giờ thường xuyên về tình hình vật giá hơn trước. Trước đây trong bữa cơm, nhà tôi hay nói về công việc của mỗi người, về những sự kiện vãn hóa xã hội nổi bật. Còn bây giờ là về giá thịt heo đã tăng bao nhiêu, giá vàng lên cao sẽ ảnh hưởng thế nào đến kinh tế. Tôi hiểu được vì sao có sự thay đổi đó độ chừng 1 tuần sau khi về lại Sài Gòn, khi bắt đầu thấm được những đổi thay về mọi mặt của thành phố.

Hôm đầu tiên khi tôi đi xe máy ra đường, mẹ tôi đưa cho chiếc mũ bảo hiểm, dặn dò kỹ lưỡng vì sợ tôi mới đi xe lại chưa quen. Ba tôi thì dúi vào tay một ít tiền, bảo rằng lãnh lương rồi ba sẽ cho thêm. Tối hôm sau đó, nhà tôi và nhà vợ tôi hợp lại ăn một bữa cơm gia đình, mừng hai đứa tôi về chơi. Bố vợ tôi, vẫn như những lần họp mặt trước đây, làm món đặc sản của ông là dồi heo. Tuy mẹ vợ tôi phải nấu chín mắm tôm để chấm vì e ngại dịch tả, nhưng tôi vẫn cảm nhận được hết cái hương vị thơm ngon của miếng dồi ăn với rau húng và ngò gai. Gia đình hai bên, cộng cả thằng em trai tôi, cả bà chị vợ tôi và ông anh cột chèo của tôi hôm ấy thật vui nìềm vui sum họp trong không khí đầm ấm, hạnh phúc như từ trước đến giờ không biến động.

Tối hôm đó, tôi thắp nhang bàn thờ tổ tiên. Mâm trái cây bên trái, bình hoa cúc bên phải và hai cây đèn cầy đỏ vẫn ở hai bên như trước khi tôi rời Sài Gòn đi sang vùng đất lạ. Tôi châm nhang rồi cắm vào lư đặt chính giữa bàn thờ. Mùi nhang thơm quyện vào không khí cùng với cái nhìn từ ái của những bậc tiền nhân như nhủ với tôi rằng: “Có những thứ mà Sài Gòn sẽ chẳng bao giờ thay đổi…”.

Sài Gòn – 2008

Chuyên mục: Chưa phân loại | Bình luận (14) »

R.I.P. Michael Jackson

Ngô Quang Hưng | 25 tháng 06, 2009 | Bản để in

Chỉ có hai M.J. lừng danh trên thế giới này. Một là cầu thủ bóng rổ. Hai là anh. Cho dù phần sau cuộc đời M.J. hơi nhiều “drama”, và có vẻ tâm thần anh không ổn định, điều đó chưa và không bao giờ làm giảm tầm ảnh hưởng âm nhạc của ông vua pop.

Chuyên mục: Tin tức đó đây & Âm Nhạc | Bình luận (3) »

PCP 9 — Expanders: tích zig-zag

Ngô Quang Hưng | 25 tháng 06, 2009 | Bản để in

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}$ và ${H}$ là ${(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}$ và ${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}$ và ${\beta<1}$ . Nôm na là, nếu ${G}$ và ${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}$ là ${(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$ .

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}$ là ${2}$ và tên ở đầu ${v}$ là ${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}$ và ${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}$ có ${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}$ là ${\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)}$ là ${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à ${(v_1,v_2)}$ là kề nhau nếu và chỉ nếu ${u_1v_1\in E_1}$ và ${u_2v_2\in E_2}$ .

Bài tập: chứng minh rằng nếu ${G_1}$ và ${G_2}$ là ${(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}$ là ${(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)|))}$ .

Chuyên mục: Lý thuyết tính toán & Thuật Toán | Bình luận »

Blog Mới

Ngô Quang Hưng | 24 tháng 06, 2009 | Bản để in

Hòa thượng Thích Học Toán, hay còn gọi là Ngô Bảo Châu.

Thấy qua blogroll của Gvietmath.

Chuyên mục: Tin tức đó đây | Bình luận »

The Voice

Ngô Quang Hưng | 22 tháng 06, 2009 | Bản để in

(Lưu ý: video dưới đây có thể không thích hợp cho người yếu tim.)

“The Voice” = Neda Salehi Agha-Soltan

Chuyên mục: Tin tức đó đây | Bình luận »

Bản survey của anh Dương Danh Huy

Ngô Quang Hưng | 19 tháng 06, 2009 | Bản để in

Các bạn có rảnh rỗi điền giùm bản survey này của anh Đương Danh Huy, hỏi về kiến thức cơ bản về biển Đông, lệnh cấm đánh cá của Trung Quốc, và có nên chống đối hay không. Tôi nghĩ kết quả sẽ rất thú vị.

Cập nhật: đã có một số kết quả

Kết quả survey của các bạn đọc talawas
Kết quả survey của một số blogs (bao gồm blog KHMT)
Kết quả survye của các bạn đọc Minh Biện

Chuyên mục: Thông báo | Bình luận (8) »

Vài bài viết hay nhân ngày báo chí

Ngô Quang Hưng | 16 tháng 06, 2009 | Bản để in

Chưa đến ngày báo chí, nhưng thấy bên Talawas có bài của Thiện Ý hay và nhiều thông tin, dù đa phần đã biết rải rác:

Trích một đoạn trong phần 2:

Nếu luật pháp Việt Nam chưa đủ chặt chẽ để ngăn chặn các hành vi “lợi dụng chi phối” ấy thì chúng ta nên gấp rút hoàn thiện luật pháp để thực thi cho được Điều 19, sẽ tốt hơn gấp trăm lần cấm đoán! Hay là chúng ta sợ mình không đủ lý lẽ chống lại sự ngụy biện xuyên tạc của kẻ xấu? Trong lịch sử không có chính nhân quân tử nào lại sợ kẻ xấu cả! Ngụy biện xuyên tạc là hành vi mờ ám, chỉ cần soi ánh sáng của sự thật vào là nó sẽ vỡ vụn ngay. Chẳng lẽ chúng ta sợ những ý kiến phản biện? Trong tuyên bố ngày 24 tháng 1 năm 2006, Tổng Bí thư Nông Đức Mạnh có một câu rất hay (đúng ra là có tinh thời đại): “Tôn trọng những ý kiến khác biệt”. Tôn trọng ý kiến khác biệt thì phải chấp nhận tranh luận, để tìm ra chân lý! Người lớn, cấp cao chịu làm như vậy không hề hạ thấp mình mà càng được “khẩu phục tâm phục”.

Còn bài mới này bên blog Osin

Có một câu chuyện, có lẽ, mang tính ngụ ngôn nhiều hơn, nói về cách những người đi rừng chống lại đười ươi. Chuyện kể: Mỗi khi chụp được người, con đười ươi sẽ nắm chặt hai tay rồi ngửa mặt lên trời nhắm mắt mà cười; đợi trời tối mới “xử lý”. Những người đi rừng kinh nghiệm, ai cũng mang theo hai ống vầu cỡ bằng ống tay, bị đười ươi bắt thì đưa ống vầu cho đười ươi nắm. Khi con vật ấy ngửa mặt lên trời, đắc chí cười, thì lẳng lặng bỏ đi. Con đười ươi tưởng nắm được tay nhưng thực ra chỉ nắm được hai ống vầu con mồi chìa cho ấy.

Báo chí Việt Nam, cho dù được xác định là “công cụ”, thì từ chính quyền đi tới nhân dân báo chí chỉ có tác dụng khi trở thành “cánh tay” thực sự. Thấy dân kêu mà không lên tiếng; thấy chính sách chưa thích hợp mà không phân tích; thấy vận nước bị đe dọa mà vẫn sớm tụng, chiều ca… thì “công cụ” ấy chỉ ru ngủ những ai “nắm” chúng.

Chuyên mục: Nhân vật và sự kiện | Bình luận (5) »

Rajeev Motwani qua đời

Ngô Quang Hưng | 06 tháng 06, 2009 | Bản để in

Hừm, vừa biết tin qua complexity blog

I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a swimming pool accident at his home. He will be remembered by the large number of professional colleagues, faculty colleagues, and students whose education and lives have been enriched tremendously by his.

Motwani là đồng tác giả (một trong hai) bài báo chứng minh định lý PCP, đồng tác giả bài báo PageRank với Brin & Page (xem obituary của Brin vừa viết), và đóng vai trò quan trọng trong việc tư vấn khởi tạo Google. Ông cũng là đồng tác giả quyển textbook rất phổ dụng: Randomized Algorithms

Chuyên mục: Tin tức đó đây | Bình luận (1) »

Internet

Ngô Quang Hưng | 06 tháng 06, 2009 | Bản để in

Tặng các chiến binh máu lửa

Chuyên mục: Vui - Giải Trí | Bình luận (1) »

Đẹp ná thở (2)

Ngô Quang Hưng | 05 tháng 06, 2009 | Bản để in

Cảm ơn bạn Hoàng đã giới thiệu (xem thêm bên Nhiệt Huyết).

Xem cái này, và bớt xả rác, dùng ít giấy và túi nylon lại, tắt đèn và máy tính đi, một hôm thôi cũng được, nhé!

Chuyên mục: Quả đất của ta | Bình luận »

Тетрис

Ngô Quang Hưng | 02 tháng 06, 2009 | Bản để in

25 tuổi. Ồ, và khó xấp xỉ nữa.

Twenty-five years ago, inside the bowels of the Soviet Academy of Sciences in Moscow, a young artificial intelligence researcher received his first desktop computer – the Soviet-built Elektronika 60, a copy of an American minicomputer called a PDP-11 – and began writing programs for it.

But not numerical ones. He ended up creating one that would infest the dreams of those who played it, spurring addictions and even the suspicion that it was a Russian plot to divert the youth of America in a pointless exercise.

Chuyên mục: Tin tức đó đây & Vui - Giải Trí | Bình luận »

Google Wave + Wolfram Alpha

Ngô Quang Hưng | 01 tháng 06, 2009 | Bản để in

Thời gian gần đây, hai công cụ online rất hữu dụng cho dân làm Toán/KHMT đã và sẽ ra đời.

Đã ra đời là Wolfram Alpha, cực kỳ tiện cho những tác vụ “quick & dirty”. Muốn tìm $\max (1-(1-x)^3)(1-x)^5, \ x\in [0,1]$ thì gõ cái này là xong. Chưa tý toáy lâu, có vẻ còn nhiều chức năng khác.

Sẽ ra đời là Google Wave. Xem video giới thiệu ở đây (biết qua Terry Tao’s blog):

Chuyên mục: Tin tức đó đây | Bình luận »

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

Ngô Quang Hưng | 31 tháng 05, 2009 | 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ố $d,\alpha>0$ , một chuỗi các đồ thị $\{G_i\}_{i=1}^\infty$ là một họ $(d,\alpha)$ của các spectral expanders nếu $G_i$ là $(n_i,d,c)$ -spectral expander. Trong đó, $n_1<n_2 <\dots$ , và tồn tại một đa thức $g(n)$ sao cho $n_{i+1} = O(g(n_i))$ với mọi $i$ . Điều kiện cuối cùng này chỉ để giới hạn kích thước của các expanders trong họ. Cái sau không thể có kích thước bằng số mũ của cái trước.

Trong đa số các ứng dụng (xem dưới đây), cho trước một hằng số $\alpha<1$ , chúng ta muốn là có một hằng số $d$ sao cho một họ $(d,\alpha)$ của các spectral expanders tồn tại, và mỗi thành viên trong họ có thể xây dựng được trong polynomial time.

Định nghĩa. (Họ expanders xây dựng tương đối cụ thể)

Một họ $\{G_i\}$ của các expanders có thể xây dựng được một cách tương đối cụ thể (mildly explicit) nếu tồn tại một thuật toán mà cho input là $i$ nó output đồ thị $G_i$ trong thời gian $\text{poly}(i)$ .

Ví dụ: có thể xây dựng một họ các expanders như sau. Gọi $n_i$ là số nguyên tố thứ $i$ . Đặt $V(G_i) = \mathbb Z_{n_i}$ (nhóm Abel). Với một đỉnh bất kỳ $x \in \mathbb Z_{n_i}$ thì nối $x$ với các hàng xóm $x+1,x-1,x^{-1}$ . Trong đó, các phép tính cộng, trừ, nghịch đảo là tính trên nhóm. Và, ta định nghĩa nghịch đảo của $0$ là $0$ . Đáng lẽ, ta có thể xây dựng đồ thị thứ $i$ rất nhanh, nhưng vì không biết cách nào để sinh số nguyên tố thứ $i$ ngoài cách cơ bắp (thử từng số từ $1$ trở đi và dùng thuật toán AKS), cho nên tổng thời gian chạy để sinh ra đồ thị thứ $i$ là $\text{poly}(i)$ .

Định nghĩa. (Họ expanders xây dựng rất cụ thể)

Một họ $\{G_i\}$ của các expanders có thể xây dựng được một cách rất cụ thể (strongly explicit) nếu tồn tại một thuật toán mà cho input là $i$ , đỉnh $v \in [n_i]$ , và số $k \in [d]$ , thuật toán in ra hàng xóm thứ $k$ của đỉnh $v$ trong đồ thị $G_i$ trong thời gian $\text{poly}(\log i, \log n_i, \log d)$ (đại khái là thời gian đa thức trong tổng số bits để biểu diễn bộ ba $(i,n_i,d)$ .