2023 ACM Turing Ödülü Prof. Avi Wigderson’a verildi

 (awards.acm.org)
1 puan yazan GN⁺ 2024-04-12 | 1 yorum | WhatsApp'ta paylaş
  • ACM, Avi Wigderson’ı 2023 ACM A.M. Turing Award sahibi olarak seçti; hesaplama kuramına ve hesaplamada rastgeleliğin rolüne dair anlayışı yeniden şekillendiren katkılarını takdir etti
  • Institute for Advanced Study’de Herbert H. Maass Professor olan Wigderson, hesaplama karmaşıklığı kuramı ile algoritmalar, kriptografi, paralel ve dağıtık hesaplama, kombinatorik ve çizge kuramında geniş çapta öncülük etmiş bir isim
  • Temel başarısı hardness for randomness araştırmaları; yaygın kabul gören hesaplamalı varsayımlar altında olasılıksal polinom zamanlı algoritmaların deterministik olarak simüle edilebileceğini göstermesi
  • İlgili makaleler sözde rastgele sayı üreteçleri, BPP’nin alt-üstel zamanlı simülasyonu ve hardness-vs-randomness ödünleşimini ortaya koyarak teorik bilgisayar biliminin birçok alanını etkiledi
  • Google’ın desteğiyle Turing Award kapsamında 1 milyon dolar ödül veriliyor; Wigderson yalnızca teknik başarılarıyla değil, genç araştırmacılara yol gösteren bir mentor olarak da değerlendiriliyor

ACM Turing Award’a seçilme arka planı

  • ACM, Avi Wigderson’ı 2023 ACM A.M. Turing Award sahibi olarak seçti
  • Ödül gerekçesi; hesaplama kuramına yaptığı temel katkılar, hesaplamada rastgeleliğin rolüne dair anlayışı yeniden kuran çalışmaları ve teorik bilgisayar biliminde onlarca yıl boyunca sergilediği entelektüel liderlik
  • Wigderson, New Jersey Princeton’daki Institute for Advanced Study matematik bölümünde Herbert H. Maass Professor olarak görev yapıyor

  • Başlıca çalışma alanları

    • Hesaplama karmaşıklığı kuramı
    • Algoritmalar ve optimizasyon
    • Rastgelelik ve kriptografi
    • Paralel ve dağıtık hesaplama
    • Kombinatorik ve çizge kuramı
    • Teorik bilgisayar bilimi ile matematik ve bilim arasındaki bağlantılar
    • ACM A.M. Turing Award, “bilişimin Nobel’i” olarak anılıyor ve Google, Inc.’in mali desteğiyle 1 milyon dolar ödül sunuyor
    • Ödül, bilişimin matematiksel temellerini atan İngiliz matematikçi Alan M. Turing’in adını taşıyor

Teorik bilgisayar biliminin ele aldığı sorular

  • Teorik bilgisayar bilimi, bilgisayar biliminin matematiksel temellerini ele alır; “Bu problem hesaplama yoluyla çözülebilir mi?”, “Çözülebilirse ne kadar zaman ve kaynak gerekir?” gibi sorularla ilgilenir
  • Bu alan, verimli algoritma tasarım ilkelerini de araştırır
  • Algoritmalar, günlük hayatta kullanılan bilişim teknolojilerini mümkün kılan temeldir
  • Teorik bilgisayar bilimi, doğrudan pratik uygulamaları iyileştirmeyen entelektüel meydan okumaları da ele alır; ancak araştırma atılımları birçok alanda ilerlemeye yol açabilir
    • Kriptografi
    • Hesaplamalı biyoloji
    • Ağ tasarımı
    • Makine öğrenimi
    • Kuantum bilişim

Hesaplamada rastgelelik neden önemli?

  • Bilgisayarlar temelde deterministik sistemlerdir; belirli bir girdi için algoritmanın komut kümesi hesaplamayı ve çıktıyı tekil olarak belirler
  • Rastgelelik, olaylarda veya sonuçlarda belirgin bir desenin ya da öngörülebilirliğin bulunmaması durumunu ifade eder
  • Gerçek dünyada hava sistemleri, biyolojik olgular ve kuantum olayları gibi rastgele görünen çok sayıda olay vardır
  • Bilgisayar bilimcileri, verimliliği artırmak için algoritmaları hesaplama sürecinde rastgele seçimler yapacak şekilde genişletti
  • Verimli deterministik algoritmaları bilinmeyen birçok problem, küçük bir hata olasılığına sahip olasılıksal algoritmalar ile verimli şekilde çözülebilir
    • Bu hata olasılığı verimli biçimde azaltılabilir
  • Temel soru, rastgeleliğin zorunlu olup olmadığı, ortadan kaldırılıp kaldırılamayacağı ve olasılıksal algoritmaların başarısı için gereken rastgeleliğin niteliğinin ne olduğudur
  • Hesaplamada rastgelelik ve sözde rastgeleliğin davranışını daha iyi anlamak, daha iyi algoritmalar geliştirmeye ve hesaplamanın doğasını kavramaya katkı sağlayabilir

Wigderson’ın temel araştırma katkıları

  • Wigderson, 40 yıl boyunca teorik bilgisayar bilimi araştırmalarına yön veren; hesaplamada rastgelelik ve sözde rastgeleliğin rolünü anlamaya temel katkılar yapan bir isim
  • Bilgisayar bilimcileri, rastgelelik ile hesaplama zorluğu, yani verimli algoritmaları olmayan doğal problemleri belirleme işi arasında önemli bağlantılar keşfetti
  • Wigderson ve ortak yazarları, hardness for randomness konusunu ele alan etkili çalışmalar yayımladı
  • Bu çalışmalar, standart ve yaygın biçimde inanılan hesaplamalı varsayımlar altında tüm olasılıksal polinom zamanlı algoritmaların verimli şekilde deterministikleştirilebileceğini gösterdi
  • Bu sonuç, verimli hesaplama için rastgeleliğin mutlaka gerekli olmayabileceğini ortaya koyuyor
  • Bu araştırma hattı, hesaplamada rastgeleliğin rolüne ve rastgelelik hakkındaki düşünme biçimine dair yaklaşımı değiştirdi

  • 3 temsilî makale

    • Hardness vs. Randomness
      • Noam Nisan ile birlikte yazıldı
      • Yeni bir tür sözde rastgele sayı üreteci tanıttı
      • Öncekilerden çok daha zayıf varsayımlar altında rastgele algoritmaların verimli deterministik simülasyonunun mümkün olduğunu kanıtladı
    • BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs
      • László Babai, Lance Fortnow ve Noam Nisan ile birlikte yazıldı
      • hardness amplification kullandı
      • Daha zayıf varsayımlar altında bounded-error probabilistic polynomial time, yani BPP’nin sonsuz sayıda girdi uzunluğu için alt-üstel zamanda simüle edilebileceğini gösterdi
    • P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
      • Russell Impagliazzo ile birlikte yazıldı
      • Daha güçlü sözde rastgele sayı üreteçleri tanıttı
      • Neredeyse optimal bir hardness-vs-randomness ödünleşimi sundu

Etki alanı ve ek başarılar

  • Wigderson’ın üç makalesi, rastgelelik ve deterministikleştirme alanlarının ötesinde teorik bilgisayar biliminin birçok alanını etkiledi
  • Bu makalelerdeki fikirler daha sonra birçok önemli araştırmacının etkili makalelerinde kullanıldı
  • Omer Reingold, Salil Vadhan ve Michael Capalbo ile yazdığı makalede, expander graph için ilk verimli kombinatorik inşayı sundu
    • expander graph, güçlü bağlantı özelliklerine sahip seyrek bir çizgedir
    • Hem matematikte hem de teorik bilgisayar biliminde önemli uygulamalara sahiptir
  • Rastgelelik dışında Wigderson şu alanlarda da entelektüel liderlik gösterdi
    • multi-prover interactive proofs
    • Kriptografi
    • Devre karmaşıklığı

Mentorluk ve değerlendirme

  • Wigderson, çığır açan teknik katkılarının yanı sıra çok sayıda genç araştırmacıya danışmanlık yapmış saygın bir mentor ve çalışma arkadaşı olarak kabul ediliyor
  • Engin bilgisi, teknik yeteneği, ulaşılabilirliği, tutkusu ve cömertliği, seçkin genç araştırmacıların teorik bilgisayar bilimi kariyerine yönelmesini sağlayan unsurlar olarak gösteriliyor
  • ACM President Yannis Ioannidis, Wigderson’ın matematik alanında yaşam boyu başarı için en önemli onurlardan biri kabul edilen Abel Prize’ı da aldığını belirtti
  • Ioannidis, matematiğin bilgisayar biliminin temeli olduğunu ve Wigderson’ın çalışmalarının matematiğin çeşitli alt alanlarını teorik bilgisayar bilimiyle ilişkilendirdiğini değerlendirdi
  • Google Senior Vice President Jeff Dean, Wigderson’ın rastgelelik ve diğer konulardaki araştırmalarının son 30 yılda teorik bilgisayar biliminin gündemini belirlediğini söyledi
  • Dean ayrıca Wigderson’ın fikirler ve araştırma yönleri oluşturduğunu, genç araştırmacıları bu yönlerde çalışmaya motive eden bir mentor olduğunu vurguladı

Turing Award ve Wigderson’ın diğer önemli makaleleri

İlgili okumalar

1 yorum

 
GN⁺ 2024-04-12
Hacker News yorumları

  • Duyuruda bahsedilen Wigderson’ın iki önemli makalesi, iyi bilinen çevrim içi ders From Nand to Tetris’i hazırlayan profesörlerden biri olan Noam Nisan ile ortak yazılmış

    • Nisan da müthiş bir isim. Hesaplama teorisinde birinci sınıf sonuçlar elde ettikten sonra, oldukça farklı bir alan olan algoritmik oyun teorisinde de büyük etki bıraktı
      Bir insanın bu kadar çeşitli başarılar gösterebilmesi güzel; böyle bir esnekliğe izin veren sistem de etkileyici
    • Kitabı da var. Yakın zamanda 2. baskısı çıktı

  • Quanta’nın iyi bir yazısı da var: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Wigderson’a verdirdikleri pozların çeşitliliği komikti. Çok yapmacık görünüyor. “Şimdi şu sandalyeye oturun ve dalgın dalgın pencereden dışarı bakın” gibi

    • “Rastlantısallığın akıl almaz etkililiği”nin Wigderson’ı rastlantısallığın kendisinin doğası üzerine düşünmeye sevk etmesi ilginç
      Karmaşıklık sınıflarının en kötü durum performansını ele aldığını anlıyorum; ama iyi bir sözde rastgele sayı üreteci ve iyi rastgeleleştirilmiş algoritmalar olsa bile RNG + seed + problem instance birleşimlerinin hiçbirinin üstel zaman gerektirmediği nasıl kabaca kanıtlanıyor, bilmek isterdim
    • Düzeltme notuna bakılırsa ilk yazıda Wigderson’ın University of Haifa’ya gittiği söylenmiş, ama aslında İsrail’in Hayfa kentindeki Technion’dan mezun olduğu belirtiliyor
      Muhabirin bunu nasıl karıştırdığını merak ediyorum
    • “Sandalyede oturup pencereden dışarı bakma” pozu Martin Scorsese ya da Sopranos tarzı bir poz gibi. Huzurevindeki yaşlı bir gangster sahnesi sanki

  • Scott Aaronson, Avi Wigderson’ın bir dersinin kendi kariyer yolunu nasıl etkilediğini yazmış: https://scottaaronson.blog/?p=2925

  • “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness” başlıklı yazıda ek bilgiler var: [1] ve arşiv kopyası [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Wigderson’ın araştırmalarında zorluk ve rastlantısallık takası tarafını yakalamak için nereden başlamak iyi olur merak ediyorum
    Turing Ödülü alan birini hiç duymamış olmak pek sık olmuyor; bu kişi tamamen görüş alanımın dışındaymış

    • Onun kitabına bakabilirsiniz: https://www.math.ias.edu/avi/book
    • “Standart ve yaygın olarak inanılan hesaplama varsayımları”nın ne olduğunu merak ediyorum
      Muhtemelen NP-tam problemler için olasılıksal yaklaştırmanın da polinom zamanda olmadığı anlamına geliyor diye düşünüyorum; yoksa rastlantısallığı çıkarılmış sürümün de hâlâ bir yaklaştırma algoritması olduğu mu kastediliyor, kafam karıştı

  • Wigderson’ın kitabını yeni elime aldım; şu ana kadar hoşuma gitti: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Kişisel araştırma ve eğitim amaçları için kitabın son taslağı burada görülebilir: https://www.math.ias.edu/avi/book
    • Kitaba baktım; yüksek lisans/doktora öğrencileri ya da ileri düzey lisans öğrencileri için daha uygun bir seviyede görünüyor
      Bilgisayar bilimi/matematik lisans altyapısı biraz paslanmış biri için hesaplama konularını daha temelden ele alan bir kitap önerebilir misiniz merak ediyorum

  • İlgili makalede şöyle bir cümle var: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “Bir önerme kanıtlanabiliyorsa, onun bir sıfır bilgi kanıtı da vardır” denmesi insanın beynini yakıyor
    Ayrıca “rastgele bitler yerine sözde rastgele bitleri olasılıksal bir algoritmaya verirseniz, aynı problem için verimli bir deterministik algoritma elde edilir” ifadesi de inanılmaz derecede şaşırtıcı
    Yapay zeka da olasılıksal hesaplama olduğuna göre, doğru okuduysam bu mevcut modellerin karmaşıklığını birkaç basamak azaltabileceğimiz anlamına gelmiyor mu? Acemi yanılgısıysa biri beni bundan kurtarsın

    • Tam olarak ne anlama geldiğini bilmiyorum ama en azından o anlama gelmiyor. Yapay zeka zaten sözde rastgelelik kullanır ve deterministiktir
      Verimliliği artırmak için analog hesaplama kullanan sıra dışı yapay zeka hızlandırıcı çipler gibi istisnalar var
    • Ne yazık ki hayır. Birincisi, bu sonuç arama problemlerine değil karar problemlerine uygulanır
      İkincisi, ortaya çıkan deterministik algoritma, rastgeleleştirilmiş algoritmadan çok daha az verimlidir. Yalnızca zayıf varsayımlar altında aynı karmaşıklık sınıfına aittir

  • Yazıdaki şu kısmı sevdim: “Uygulama motivasyon değil, ama temel araştırmada da kullanım alanı bulunabileceğini biliyorum. Alan Turing’i düşünün. Entscheidungsproblem üzerine mantık matematiği makalesini pek tanınmayan bir dergide yazdı. Motivasyonu uygulama değildi”
    Feynman’ın tabak anekdotuna benziyor. Üniversite yemekhanesinde gördüğü bir şeye hafifçe tepki vermesiyle başlayıp sonunda Nobel Ödülüne uzanmıştı
    Daha geniş anlamıyla, modern akademi tam da bu tür merak temelli araştırmayı bastırma yönüne gidiyor

  • ACM’ye göre Avi Wigderson, hesaplamada rastlantısallığın rolüne dair anlayışı yeniden şekillendirmek de dahil olmak üzere hesaplama teorisine temel katkıları ve teorik bilgisayar biliminde onlarca yıl süren entelektüel liderliği nedeniyle 2023 ACM A.M. Turing Award’un sahibi seçildi
    Wigderson, New Jersey Princeton’daki Institute for Advanced Study matematik bölümünde Herbert H. Maass Professor’dır; hesaplama karmaşıklığı teorisi, algoritmalar ve optimizasyon, rastlantısallık ve kriptografi, paralel ve dağıtık hesaplama, kombinatorik, grafik teorisi, teorik bilgisayar bilimi ile matematik ve bilim arasındaki bağlantılar gibi alanlarda kilit bir isim olmuştur
    2021’de Abel Ödülü’nü de aldığı için, teorik/soyut matematik ve bilgisayar biliminin en büyük onurlarını birlikte alan oldukça özel bir birleşim ortaya çıkıyor

    • Teorik bilgisayar bilimi ile matematiğin kesişimi çoğu kişinin bildiğinden çok daha büyük
      Basit bir örnek olarak MIT’nin teorik bilgisayar bilimi ders listesine https://catalog.mit.edu/subjects/6/ bakarsanız, derslerin ne kadarının matematik olan course 18 ile çapraz açıldığını görebilirsiniz
    • Kesin konuşmak gerekirse matematiğin en büyük onuru Fields Medal’dır
      Tabii bunu söylemek bana düşmez ama

  • Olasılık/rastlantısallık ve hesaplama konusunda başlangıç dostu kaynaklardan ileri düzeye kadar çalışmaya değer kaynak önerileri merak ediyorum
    Google’da Eli Upfal ve Michael Mitzenmacher’ın “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” kitabı çıkıyor, ama başlangıç/giriş seviyesi kitap, yazı veya video pek bulamadım