Pasin Manurangsi: Bilgisayarların Yapamadığını Kanıtlamak

Temmuz 2011'de Tayland'ın tatil şehri Pattaya, Tayland'ın ev sahipliği yaptığı ilk etkinlik olan 23. Uluslararası Bilgisayar Olimpiyatı'na (IOI) sahne oldu ve Başbakan Abhisit Vejjajiva son resmi görevlerinden biri olarak oyunların açılışını yaptı. Ev sahibi ekip arasında, 303 yarışmacı arasından 524 puanla 14. olan ve üst üste ikinci altın madalyasını toplayan Bangkok Hristiyan Koleji'nden (Bangkok Christian College) bir öğrenci vardı. Muhabirlere 14. sıradan memnun olduğunu, 524 puanın beklediğinden daha fazla olduğunu ve olimpiyatlara ev sahipliği yapmanın Taylandlı gençler arasında bilgisayarlara olan ilgiyi artıracağını umduğunu söyledi. On beş yıl sonra Pasin Manurangsi (Pasin Manurangsi), görevi geri kalan bilgisayar bilimi camiasına hangi problemlerin umutsuz olduğunu söylemek olan araştırmacılardan biri.

Olimpiyat Yayındaki Yolculuk

Manurangsi'nin rekabetçi kaydı, kontrollü bir gelişim deneyi gibi okunuyor. Bulgaristan'daki 2009 IOI'da 516 puan aldı ve 301 kişi arasından 67. olarak gümüş madalya kazandı. 2010 yılında Kanada'da 704 puan aldı ve 297 kişi arasından 12. olarak altın madalya kazandı. 2011 yılında kendi evinde, Tayland'ın ilk kez ev sahipliği yaptığı yarışmada takım altın madalyasını kazanmasıyla tekrar altın madalya kazandı. Üç katılım, iki altın ve bir gümüş madalya ve ilk ile ikinci denemesi arasında dünya sıralamasında elli beş basamak yükseliş: Kaybı bir hükümden ziyade bir şartname belgesi olarak değerlendiren birinin yörüngesi.

MIT ve Yeterince Yaklaşma Problemi

Manurangsi, hem lisans hem de yüksek lisans derecelerini, Dana Moshkovitz'in danışmanlığında yürüttüğü yüksek lisans çalışmasının izdüşüm oyunları (projection games) için yaklaşık algoritmalarla ilgili olduğu Massachusetts Teknoloji Enstitüsü'nde (MIT) aldı. Bu konu seçimi, takip eden her şeyin yönünü belirledi. Yaklaşıklık, disiplinin pragmatik uzlaşısıdır: bir problem makul sürede tam olarak çözülemediğinde, en iyinin belirli bir faktörü dahilinde olacağı garanti edilen bir cevaba razı olursunuz. İlginç olan ve Manurangsi'nin sürekli geri döndüğü soru, matematiksel bir duvara çarpmadan önce bu garantinin ne kadar iyi olabileceğidir.

Berkeley: P ve NP Arasındaki Ülke

Doktorasını Mayıs 2019'da, Luca Trevisan ve Prasad Raghavendra'nın eş danışmanlığında, Nikhil Srivastava'nın komitede yer aldığı Kaliforniya Üniversitesi, Berkeley'de (University of California, Berkeley) tamamladı. Tezin başlığı Yaklaşıklık ve Zorluk: P ve NP'nin Ötesinde (Approximation and Hardness: Beyond P and NP) idi ve hırsı başlığında görülebiliyordu. Klasik karmaşıklık teorisi problemleri çözülebilir (P) ve meşhur zor (NP-tam) olarak sınıflandırır. Manurangsi'nin tezi, bu kategorilerin kapsamadığı arazilerde kasıtlı olarak avlanmaya çıktı: P'de olmayan ve NP-zor olduğu da bilinmeyen problemler, k-baskın küme (k-dominating set), k-klik (k-clique), k-biklik (k-biclique), yönlendirilmiş Steiner ağı (directed Steiner network) ve kafes problemleri gibi parametreli problemler ve en önemlisi sezgisel olarak, en yakın çift (closest pair) ve maksimum iç çarpım (maximum inner product) gibi P'nin içinde rahatça duran ancak yine de hızlı yaklaşıklığa direnen problemler. Özet, çalışmanın parametreli karmaşıklıkta (parameterized complexity) uzun süredir açık olan iki soruyu çözdüğünü ve çeşitli problemler için en iyi bilinen yaklaşılamazlık faktörlerini sunduğunu iddia ediyor. Bu, sınırları geçmekle değil, onları çizmekle ilgili bir tez.

En Yoğun k-Alt Çizge Duvarı

Adını duyuran tek sonuç, 'En Yoğun k-Alt Çizge' (Densest k-Subgraph) ile ilgilidir: bir ağ verildiğinde, bağlantıları en sıkı olan k düğümü bulun. Manurangsi, üstel zaman hipotezi (exponential time hypothesis) altında, hiçbir polinom zamanlı algoritmanın n'in 1/(log log n) kuvvetinin sabit katından daha iyi bir yaklaşık oran elde edemeyeceğini ve daha güçlü Gap-ETH varsayımı altında engelin sıfıra yaklaşan herhangi bir f fonksiyonu için n^f(n)'e daraldığını kanıtladı ki bu neredeyse polinom zorluğuna eşittir. Önemli olan, yapının alanın 'mükemmel tamlık' (perfect completeness) dediği şeye sahip olmasıdır: gerçekten bir k-klik içeren çizgeleri, her k-alt çizgenin seyrek olduğu çizgelerden ayırt eder. Makale, disiplinin amiral gemisi teorik konferansı olan STOC 2017'de Danny Lewin En İyi Öğrenci Makalesi Ödülü'nü (Danny Lewin Best Student Paper Award) kazandı.

Google, Gizlilik ve Adil Paylaşım

Temmuz 2019'dan beri Manurangsi, Google Research'te listelenen alanları algoritmalar ve teori, makine zekası ve kötüye kullanım karşıtlığı olan ve yüzün üzerinde yayını biriktirdiği bir araştırma bilimcisidir. Ağırlık merkezi, saf yaklaşılamazlıktan diferansiyel gizliliğe (differential privacy), öğrenme teorisine ve hesaplamalı sosyal seçime - adil bölüşüm, konsensüs yarıya indirme, özel rütbe toplama, sentetik veri üretimi - kaymıştır. Yakın tarihli bir sonuç, monoton faydaları olan n aracı için O(√(n log n)) mala kadar konsensüs yarıya indirmenin her zaman mevcut olduğunu göstererek önceki bir sınırı geliştiriyor. Ödüller gelmeye devam etti: WAOA 2021'de En İyi Makale, ALT 2021'de En İyi Öğrenci Makalesi, FORC 2026'da En İyi Makale ve En İyi Makale Mansiyonu, ayrıca 2021 ve 2023'te IJCAI'de seçkin program komitesi takdiri ve NeurIPS 2023'te en iyi hakem statüsü.

Dönüş Yolculuğu

2022'den beri Tayland'ın Bilgisayar Olimpiyatı ve matematik olimpiyat kampları için koçluk ekiplerinin bir parçasıdır ve 2024 IOI'da Tayland için konuk delegasyon üyesi olarak görev yapmıştır. 2023'ten beri CMKL Üniversitesi'nde yardımcı öğretim üyesi olarak algoritma, veri yapıları ve gizlilik koruma algoritmaları dersleri vermektedir. Onu üreten boru hattı, şimdi yönetmesine yardım ettiği bir boru hattıdır.

Pasin Neden Dahi Olarak Adlandırılıyor

Buradaki bilişsel kalite alışılmadık derecede spesifiktir ve saf hız değildir. Olimpiyat başarısı, saat altında hızlı, doğru problem çözmeyi ödüllendirir; yaklaşıklık zorluğu tam tersini ödüllendirir - tüm bir algoritma sınıfının mahkum olduğunu kanıtlayan ayrıntılı bir indirgeme oluşturma sabrı. Manurangsi, her ikisini de yüksek seviyede yapma konusunda nadirdir ve Berkeley tezi bunun kanıtıdır: çoğu araştırmacının tam olarak negatif sonuçların yayınlanmasının daha zor olması ve doğru elde edilmesinin daha zor olması nedeniyle kaçındığı bir bölgeyi işaretler. İndirgemede tek bir mantıksal kayma her şeyi geçersiz kılar.

Dürüst karşı tez önemlidir. Kaynaklı kayıtlarda hiçbir şey - kendi ana sayfası, Google Research profili, tez veya çağdaş Tayland basını - onun hakkında 'dahi' kelimesini kullanmaz. Onur ödülleri, odadaki en iyi makaleyi tanıyan, çağlar için bir zihni değil, konferans komitelerinden gelen meslektaş ödülleridir. Teorik bilgisayar bilimi aynı zamanda amansızca işbirlikçidir; yüzün üzerindeki makalesi ortak yazarlık, seminerler ve alanın en güçlü iki karmaşıklık teorisyeni tarafından yönetilen bir Berkeley grubunun ürünüdür. IOI kaydı, mükemmel olsa da, 67. sırayı içerir. Enflasyon olmadan söylenebilecek şey daha dar ve daha ilginçtir: matematiğin teknik açıdan en talepkar köşelerinden birinde birinci sınıf bir profesyoneldir ve tanımlayıcı sonucu yıllardır açık olan bir soruyu kapatmıştır. Bu, dahi olmakla aynı şey değildir ve o asla böyle bir iddiada bulunmamıştır.

Görünüm

Manurangsi'nin kariyeri bir teorisyen için alışılmadık bir şekle sahiptir: imkansızlık kanıtları önce, uygulamalı gizlilik çalışması ikinci geldi. Diferansiyel gizliliğe ve adil bölüşüme geçiş, duvarların nerede olduğunu belirledikten sonra artık onların içinde inşa etmeyi tercih edecek birini öneriyor. Tayland olimpiyat koçluğu daha kalıcı bir miras olduğunu kanıtlayabilir - bir kez IOI'ye ev sahipliği yapan ve şimdi onu kazanan insanları yetiştiren bir ülke.