PhD Life sucks! Chém gió sau deadline

Trong blog chủ yếu là các bài viết kĩ thuật. Post này là bài đầu tiên về công việc cá nhân, mặc dù vẫn dính dáng một tí đến kĩ thuật. Hôm nay tự nhiên có hứng nên post luôn, nếu không mấy hôm nữa lại không viết được. Có khi hôm đẹp trời nào đó đọc lại post này mình lại đóng post cũng nên. Thực ra trong thư mục draft của mình cũng có vài bài cá nhân, nhưng chưa bao giờ những bài đó được hoàn thành vì sau những dòng đầu tiên thì bị cụt hứng không viết tiếp được.

Warning: Post này khoe khoang là chính, nhưng mình vẫn cố gắng kiềm chế cảm xúc để bớt tính bốc phét của bài viết.

Chả là hôm nay vừa submit một bài đầu tiên vào FOCS. Danh tiếng của FOCS thì trong ngành lý thuyết khoa học máy tính (gọi tắt là lý thuyết) thì không phải bàn. Nói đến lý thuyết thì có 3 hội nghị chính: STOC, FOCS và SODA.

Với một số outstanding student thì việc có bài trong mấy hội nghị này không phải vấn đề lớn, ví dụ anh này có cả đống. Còn với một sinh viên bình thường (hi vọng là bình thường) như chủ thớt đây chẳng hạn thì một bài là ấp ủ từ lâu. Mặc dù mới chỉ là submit (accept hay không thì còn phải đợi vài tháng nữa), nhưng câu chuyện đầy đủ tại sao mà có kế quả này thì xin kể ra đây.

Kết quả trong bài báo submit mà mình (và 2 người khác nhưng thôi tạm gọi là mình chung cho cả 3) là về bài toán người du lịch. Bạn nào học CS thì đều biết bài này, nhưng vẫn xin mô tả ngắn gọn như sau:

TSP: N thành phố, khoảng cách giữa thành phố thứ i và thứ jd_{i,j}. Một người bắt đầu từ thành phố đầu tiên, và muốn đi thăm tất cả các thành phố khác, mỗi thành phố ít nhất 1 lần, và sau đó quay trở lại thành phố xuất phát. Tìm một chu trình ngắn nhất cho người đó.

 

Bài toán này có thể nhìn qua góc độ đồ thị như sau: mỗi đỉnh là một thành phố và cạnh nối hai thành phố có độ dài là khoảng cách giữa hai thành phố.

Bài toán này là một trong những bài toán rất khó, làm đau đầu các nhà nghiên cứu bao nhiêu năm nay. Đây là một bài toán NP-hard, nghĩa là cho tới hiện tại người ta vẫn không tìm ra được thuật toán hiệu quả để giải bài toán này. Ở đây đang nói đến tìm lời giải chính xác, i.e, tìm chu trình ngắn nhất.

Không giải được chính xác thì ta xấp xỉ vậy. Giải thuật Christofides năm 1976 luôn đảm bảo tìm được chu trình với độ dài không quá 3/2 độ dài của chu trình ngắn nhất. Cho đến gần đây người ta mới phát hiện thuật toán cực kì phưc tạp tìm được chu trình độ dài không quá \frac{3}{2}-\epsilon với \epsilon là một phần tỉ tỉ tỉ (không nhớ rõ là bao nhiêu chữ tỉ). Và một số khác chứng minh được rằng có lẽ không thể xấp xỉ tốt hơn 123/122 được.

Sau đó thì người ta tìm cách xấp xỉ TSP trong các đồ thị thực tế hơn: ví dụ đồ thị với các điểm trên cùng một mặt phẳng, đồ thị phẳng, hay đồ thị bounded-genus (mình không biết dịch từ này). Kết quả gần đây nhất là: trong các đồ thị như vậy, ta có thể tìm được một chu trình có độ dài không quá (1 + \epsilon) trong thời gian 2^{O(\frac{1}{\epsilon})}n với bất kì số \epsilon nhỏ tùy ý. Ví dụ bạn có thể tìm được chu trình với độ dài không quá 1.000001 lần đồ dài chu trình ngắn nhất (\epsilon = 0.000001) trong thời gian O(n) (mặc dù hằng số ẩn sau O(.) khá to).

Một câu hỏi bỏ ngỏ từ lâu là:

Open Problem: Liệu có tìm được chu trình với độ dài (1+\epsilon) với \epsilon nhỏ tùy ý trong thời gian 2^{p(\frac{1}{\epsilon})}n^{O(1)} trong đồ thị minor-free hay không? Ở đây p(x) là một đa thức bậc cố định.

 

Ví dụ p(x) = x^5 là một đa thức như vậy. Kết quả mà nhóm mình đang nộp là câu trả lời Yes của bài toán mở này và biến nó thành định lí!

Theorem: Tồn tại một thuật toán có thời gian 2^{p(\frac{1}{\epsilon})}n^{O(1)} tìm được chu trình với độ dài (1+\epsilon) với \epsilon nhỏ tùy ý trong đồ thị minor-free với p(x) = x^5.

 

Đồ thị minor-free là gì thì có lẽ mất cả vài chục dòng để mô tả nên mình không định nghĩa ở đây, nhưng nó là một dạng tổng quá hóa của đồ thị phẳng và đồ thị bounded-genus. Đây có lẽ cũng là loại đồ thị tổng quát nhất mà người ta hi vọng có thể xấp xỉ TSP tùy ý được.

Đồ thị minor-free có một cấu trúc nhìn rất phức tạp (xem hình dưới đây), và phải mất tới 20 năm (cùng 500 trang giấy) thì Robertson và Seymour mới chứng minh được cấu trúc như vậy. Công trình của Robertson và Seymour là một bước ngoặt trong lý thuyết đồ thị hiện đại.

minor-free
Figure 1: Hình bên trái là một đồ thị phẳng. Hình bên phải là một đồ thị minor-free (đã đơn giản hóa). Hình được sửa đổi từ đây.

Gần đây, Demaine, Hajiaghayi và Kawarabayashi tìm ra được giải thuật với thời gian O(n^{p(\frac{1}{\epsilon})}), trong khi câu hỏi mở là đưa p(\frac{1}{\epsilon}) ra khỏi lũy thừa của n. Kết quả của nhóm mình chính là như vậy.

Vài dòng trên chỉ là giới thiệu kết quả, và đó không phải là nội dung chính của bài viết này. Nội dung chính là quá trình tìm ra câu trả lời của bài toán đó.

Lan man

Mình sẽ lan man một tí về quá trình bắt đầu Ph.D life và tại sao tiêu đề của mình lại như vậy. Ph.D. life sucks! Tháng 9 năm 2013 mình chính thức bắt đầu chương trình Ph.D. Bài toán đầu tiên mà advisor của mình, giáo sư Glencora Borradaile, gợi ý liên quan tới bài toán tìm đồ thị con của một đồ thị chứa đúng k đỉnh mà có nhiều cạnh nhất. Sau 3 tháng vật vã mình bắt đầu nếm mùi. Tưởng tìm ra được gì đó hay hay, cuối cùng mới biết có người làm trước rồi, mà lại còn làm tốt hơn. Ph.D. life sucks!

Sau đó chuyển qua làm về dominating set trong đồ thị có độ rộng cây nhỏ. Câu chuyện lần này còn thú vị hơn nữa. Sau 2 tháng (lúc này là năm 2014) ra được một kết quả để nộp vào ESA, và sau đó kết quả bị từ chối. Người bình duyệt (reviewer) cho rằng kết quả chưa đủ mạnh. Lần này dành khoảng 1 tháng cải tiến kết quả và thêm vào một kết quả mới, và quyết định nộp vào SODA. Lần này gặp lại người bình duyệt lần trước từ ESA (chính người bình duyệt nói là đã review một lần trong ESA rồi). Người bình duyệt cho rằng kết quả chưa đủ mạnh so với mức của SODA, nhưng nếu nộp vào ESA thì ông ấy sẽ đồng ý accept. Kết quả bài báo bị reject lần 2. Sau đó lại nộp vào ESA năm sau (nhưng không may không gặp người bình duyệt cũ). Một trong số bình duyệt chê là bài báo viết khó hiểu (2 người còn lại thì chả có comment gì và chỉ nói accept) và cho điểm bình duyệt thấp. Kết quả cuối cùng bị reject lần 3. Lần 4 nộp vào WADS, bị reject lần 4. Nguyên nhân là format chỉ cho phép lề của bài viết ít nhất 1.5 inch, trong khi mình để 1 inch. Sau đó bị reject tiếp lần 5 vì kết quả không ấn tượng. Đó là cuối năm 2015, còn mình thì đã post bài báo lên arxiv từ cách đó lâu rồi. Mãi đến lần 6 (năm 2016) mới được accept tại IPEC. Đúng 6 lần nộp trong vòng hơn 2 năm. Ph.D. life sucks!

Quay trở lại chủ đề chính. Mình bắt đầu bài toán mở trên từ tháng 4 năm 2014 (cho đến lúc có kết quả là vừa tròn 3 năm).

Kết quả đó được tìm ra như thế nào?

Như đã nói, bài toán mình theo đuổi là về xấp xỉ TSP trong đồ thị minor-free. Giải thuật thì đã có sẵn chỉ là có phân tích được nó hay không. Phép phân tích yêu cầu chứng minh một kết quả trong lý thuyết spanner, mà mình sẽ không nói ở đây nó là cái gì. Điểm chính ở đọa này đó là thay vì tập trung vào TSP, mình chỉ cần tập trung vào các spanner là đủ.

Mình bắt đầu từ việc tìm hiểu H-minor-free là gì và cấu trúc nó như thế nào. Không có cách nào khác là đọc công trình của Robertson và Seymour, công trình đồ sộ 500 trang và được chia thành 20 bài báo viết trong vòng 20 năm, bài đầu tiên từ năm 1983 và bài cuốc cùng là năm 2004. Sau đó còn thêm một vài bài nữa nhưng về cơ bản đến bài số 20 là kết thúc. Rất may cấu trúc của đồ thị minor-free được mô tả từ bài 1 cho đến bài 14, tổng cộng hơn 300 trang. Ba tháng đọc ròng rã, và mình dừng ở bài số 14. Lúc đó cũng nắm khá rõ về cấu trúc đồ thị này. Nhìn lại thấy lúc đó trẻ trâu thật, chứ giờ mà bảo đọc công trình nào đó tương tự kiểu này thì chắc cũng xin kiếu. Không đủ kiên nhẫn như hồi đó.

Sau đó bắt đầu quay ra đọc kĩ hơn về các kết quả đã có trước cho bài toán này. Kết quả đầu tiên (và duy nhất) là của Grigni và Hung, giải quyết cho trường hợp đồ thị có bounded pathwidth. Mình không mô tả bounded-pathwidth là đồ thị như thế nào, nhưng về cơ bản nó chỉ là một lớp đồ thị rất nhỏ trong đồ thị minor-free. Tuy nhiên, phần quan trọng nhất của bài báo thì lại được mô tả khá sơ sài và khó hiểu.

Thách thức đầu tiên mà mình tự đặt ra là tự chứng minh lại kết quả của Grigni và Hung, dựa trên ý tưởng của họ, với hi vọng sẽ mở rộng được ý tưởng của họ. Sau khoảng 1 tháng thì mình đã tìm ra cách chứng minh mới, và tin rằng (tại sao mình dùng từ tin rằng thì sẽ kể sau, chi tiết khá thú vị) mình đã mở rộng được ý tưởng đó cho đồ thị có độ rộng cây nhỏ (bounded treewidth graphs). Lớp đồ thị này rộng hơn lớp đồ thị bounded pathwidth, nhưng vẫn không là gì so với minor-free graphs.

Câu hỏi tiếp theo là làm sao mở rộng ra cho minor-free graphs được. Lúc này sự hiểu biết về cấu trúc của đồ thị minor-free bắt đầu có tác dụng. Trong khoảng 3 tháng miệt mài, mình tìm ra một cách quy đồ thị minor-free về đồ thị bounded-treewidth (mà mình đã chứng minh tính chất của nó ở đoạn văn trước). Phép quy (reduction) sử dụng định lý Robertson và Seymour! Bingo! Bài toán đã xong và cuộc đời lại tươi đẹp. Ph.D. life không còn suck nữa. Lúc đó là đầu năm 2015.

Việc còn lại là viết bài và nộp cho FOCS 2015. Viết trong khoảng 1 hay 2 tháng gì đó. Mọi thứ hình như có gì đó không đúng, hơi suôn sẻ. Cuối cùng thì khó khăn thực sự lộ diện. Một tuần trước deadline, ngồi duyệt lai paper một lần trước khi nộp, phát hiện ra một lỗi logic rất cơ bản. Không hiểu sao mình lại có thể viết ra những thứ phi logic thế. Lỗi logic nằm ở chỗ mở rộng chứng minh của đồ thị bounded pathwidth ra đồ thị bounded treewidth (giờ thì bạn đã hiểu tại sao mình dùng chữ tin rằng ở trên). Còn đúng 1 tuần, tập trung hết tốc lực để sửa. Cả tuần mất ăn mất ngủ. Cuối cùng thì đến ngày deadline, mình vẫn không sửa nổi và rồi không nộp bài nữa (có đúng đâu mà nộp). Ph.D. life sucks again!

Rất may là advisor cực kì nice, cho dù thất bại nhưng vẫn động viên mình rất nhiều. Sau vài tháng tiếp tục tìm cách sửa, nhưng vẫn không có cách nào. Cuối cùng thì quyết định nộp kết quả phép quy mà mình phát hiện ra: nếu đồ thị bounded-treewidth có light spanner thì đồ thị minor-free cũng có light spanenr. Còn đồ thị bounded-treewidth có tính light spanner hay không thì vẫn không xác định đươc (vừa mới post bài báo lên arxiv cách đây vài ngày https://arxiv.org/abs/1703.10633). Mặc dù kết quả này đã giảm độ khó của bài toán ban đầu (vì đồ thị bounded treewidth chỉ là lớp rất nhỏ của đồ thị minor-free), nhưng nó vẫn không phải là một kết quả đây đủ theo đúng nghĩa. Nếu đồ thị bounded treewidth không có light spanner thì bài báo của mình chả có ý nghĩa gì. Do đó, 3 lần nộp vào 3 hội nghị thì đều bị reject cả 3 với cùng một lí do mà mình vừa nói. Ph.D. life sucks!

Trong 2 năm tiếp theo mình vẫn không bỏ cuộc, tuần nào cũng nghĩ về nó một chút. Mình có làm thêm một số bài toán khác và cũng có kết quả. Nhưng 2 năm rồi vẫn không mò ra gì thêm cho bài toán chính của mình. Các kết quả spanner cho đồ thị tổng quát thì rất nhiều, nhưng cho đồ thị minor-free thì lại không có mấy. Đến đầu năm 2017, sau khi trở về từ internship, mình và advisor bắt đầu liên hệ với Christian, giáo sư của trường đại học Copenhaghen, Đan Mạch. Giáo sư Christian là bạn của advisor mình và cũng đã publish vài bài cùng với advisor. Giáo sư Christian cũng là chuyên gia về spanner. Năm 2016, Christian và đồng nghiệp đã được giải best paper award về spanner cho đồ thị tổng quát tại SODA, một trong 3 hội nghị hàng đầu về lý thuyết. Sự cộng tác này đã dẫn đến kết quả cuối cùng. Ph.D. life lại không suck nữa!

Những email trao đổi đầu tiên với Christian chủ yếu về mô tả bài toán, một số phương pháp tiếp cận và các kết quả ban đầu mà mình và advisor đã đạt được. Nhiệm vụ còn lại chỉ là chứng minh kết quả spanner cho đồ thị bounded treewidth. Sau khi đồng ý cộng tác, mình và Christian có họp trên skype vài lần. Nửa tháng đầu tiên nhóm mình khai triển một phương pháp khác cho đồ thị bounded treewidth, nhưng rồi sau đó thấy rằng phương pháp đó không hiệu quả. Sau đó nhóm chuyển sang sử dụng phương pháp cũ của Christian và đồng nghiệp trong bài báo đoạt giải best paper award. Cuối cùng thì phương pháp này lại cho ra lời giải đẹp. Không những giải quyết được trường hợp đồ thị bounded treewidth mà còn mở rộng ra được thành một chứng minh mới cho đồ thị minor-free. Mission is completed! What an enjoyful journey! Ph.D. life lại đẹp.

Bài báo đã được submit vào FOCS cách đây vài giờ. Mọi thứ giờ chỉ là đợi kết quả, chuẩn bị cho lần nộp bài tiếp theo nếu bài báo bị reject. Cho dù kết quả hội nghị có thế nào vì mình cũng hài lòng vì "It’s all about the journey, not the destination" (mình không biết câu nói này của ai, bạn nào biết thì comment xuống dưới hộ cái).

Mình thật may mắn đã được cộng tác với advisor của mình và Christian. Mình kết bài với câu nói nổi tiếng của Pasteur "Luck favors the prepared mind."

Lê Việt Hùng
Corvallis, OR
Ngày 06/04/2017

Update 1: Ngôi sao lý thuyết mới nổi Aviad Rubinstein nhắc tới ở trên sẽ vào Stanford làm Assistant Professor Fall 2017.

Reply

Your email address will not be published. Required fields are marked *