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

• Teorik bilgisayar bilimi, bilişim alanının matematiksel temellerini ele alır. "Bu problem hesaplama yoluyla çözülebilir mi?", "Bu problem hesaplamayla çözülebiliyorsa ne kadar zaman ve kaynak gerekir?" gibi sorular sorar. Ayrıca verimli algoritmaların nasıl tasarlanacağını araştırır. Hayatımızı etkileyen tüm bilişim teknolojileri algoritmalar sayesinde mümkün olur. Güçlü ve verimli algoritmaların ilkelerini anlamak, yalnızca bilgisayar bilimini değil, doğa yasalarına dair anlayışımızı da derinleştirir. Teorik bilgisayar bilimi, ilgi çekici entelektüel meydan okumalar sunan bir alan olarak bilinir ve çoğu zaman bilişimin pratik uygulamalarını iyileştirmekle doğrudan ilişkili değildir; ancak bu alandaki araştırma yenilikleri, kriptografi, hesaplamalı biyoloji, ağ tasarımı, makine öğrenimi, kuantum hesaplama gibi neredeyse tüm alanlarda ilerlemeye yol açmıştır.

• Temelde bilgisayarlar deterministik sistemlerdir. Bir algoritmanın komut kümesi belirli bir girdiye uygulandığında hesaplama tek biçimde belirlenir ve özellikle çıktı da belirlenmiş olur. Yani deterministik algoritmalar öngörülebilir bir düzen izler. Buna karşılık rastgelelik, iyi tanımlanmış bir düzenin ya da olay/sonuçların öngörülebilirliğinin eksikliğidir. İçinde yaşadığımız dünya rastgele olaylarla dolu gibi göründüğünden (hava durumu sistemleri, biyolojik/kuantum olgular vb.), bilgisayar bilimciler algoritmaların verimliliğini artırmak için hesaplama sürecinde rastgele seçimler yapabilmelerini sağlayacak şekilde algoritmaları güçlendirmiştir. Nitekim verimli deterministik algoritmaları bilinmeyen birçok problem, olasılıksal algoritmalarla verimli biçimde çözülmüştür (küçük bir hata olasılığıyla da olsa, bu olasılık etkin biçimde azaltılabilir). Peki rastgelelik gerçekten vazgeçilmez midir, yoksa ortadan kaldırılabilir mi? Olasılıksal algoritmaların başarısı için gereken rastgeleliğin niteliği nedir?

• Avi Wigderson, 40 yılı aşkın süredir teorik bilgisayar bilimi araştırmalarına öncülük ediyor ve hesaplamada rastgelelik ile sözde rastgeleliğin rolünü anlamamıza temel katkılar sağladı. Bilgisayar bilimciler, rastgelelik ile hesaplama zorluğu (verimli algoritması olmayan doğal problemleri belirleme) arasında dikkat çekici bağlantılar keşfetti. Wigderson, çalışma arkadaşlarıyla birlikte rastgelelik karşılığında zorluğu takas etmeye dair son derece etkili bir araştırma dizisi yürüttü. Standart ve yaygın biçimde kabul gören hesaplama varsayımları altında, tüm olasılıksal polinom zamanlı algoritmaların rastgelelikten verimli biçimde arındırılabileceğini, yani tamamen deterministik hale getirilebileceğini kanıtladılar. Başka bir deyişle, rastgelelik verimli hesaplama için zorunlu değildir. Bu araştırma dizisi, hesaplamada rastgeleliğin rolüne dair anlayışımızı ve rastgelelik hakkında düşünme biçimimizi kökten değiştirdi.

Wigderson’un katkıları

• "Hardness vs. Randomness" (Noam Nisan ile ortak yazarlık): Bu makale, diğer katkılarının yanı sıra yeni bir tür sözde rastgele üreteç tanıttı ve daha önce bilinenden çok daha zayıf varsayımlar altında rastgeleleştirilmiş algoritmaların verimli deterministik simülasyonunun mümkün olduğunu gösterdi.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (László Babai, Lance Fortnow, Noam Nisan ile ortak yazarlık): Bu makale, bounded-error probabilistic polynomial time (BPP) sınıfının, "hardness amplification" kullanılarak daha zayıf varsayımlar altında sonsuz sayıda girdi uzunluğu için subexponential time içinde simüle edilebileceğini gösterdi.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (Russell Impagliazzo ile ortak yazarlık): Bu makale, özünde en uygun hardness vs randomness tradeoff’a sahip daha güçlü bir sözde rastgele üreteç sundu.

• Wigderson, rastgelelikle ilgili çalışmalarının ötesinde, çoklu kanıtlayıcılı etkileşimli ispatlar, kriptografi, devre karmaşıklığı gibi teorik bilgisayar biliminin çeşitli başka alanlarında da entelektüel liderlik sergiledi.

GN⁺ görüşü

• Rastgelelik ile hesaplama karmaşıklığı arasındaki ilişkiyi matematiksel açıdan ortaya koyan Wigderson’un çalışması, bilgisayar bilimi ile matematiğin kesişimi bakımından büyük önem taşıyor. Özellikle rastgeleliğe dayandığı düşünülen birçok algoritmanın aslında deterministik olarak aynı şekilde gerçekleştirilebileceğini göstermesi, bilgisayar biliminde yeni bir ufuk açmış olarak değerlendiriliyor.

• Ayrıca verimlilik ile zorluk arasındaki ilişkiye matematiksel bir yaklaşımla bakılması da teorik bilgisayar biliminin önemli araştırma başlıklarından biri olmaya aday görünüyor. Bir problem ne kadar zorsa, buna karşılık daha verimli bir algoritmanın var olma ihtimalinin de o kadar yüksek olabileceği fikri, sezgisel olmayan bir içgörü sunuyor.

• Öte yandan Wigderson’un teorik bilgisayar biliminin gelişimi için matematik ile bilgisayar bilimini bir araya getirmeyi vurgulaması ve genç araştırmacıların yetişmesine katkı sunması da gelecek akademik kuşaklar için iyi bir örnek niteliğinde. Özellikle hem matematiğin Abel Ödülü’nü hem de bilgisayar biliminin Turing Ödülü’nü kazanmış olması, teorik bilgisayar biliminin önemini gösteren simgesel bir örnek sayılabilir.

[GN⁺]

Hacker News görüşleri

• Avi Wigderson, 2023 ACM A.M. Turing Award'ı kazandı. Hesaplama teorisine yaptığı temel katkılar, özellikle hesaplamada rastgeleliğin rolüne ilişkin anlayışı yeniden şekillendirmesi ve onlarca yıl boyunca teorik bilgisayar bilimi alanında entelektüel liderlik sergilemesi nedeniyle ödüllendirildi.

• Wigderson; hesaplama karmaşıklığı teorisi, algoritmalar ve optimizasyon, rastgelelik ve kriptografi, paralel ve dağıtık hesaplama, kombinatorik ve grafik teorisi gibi alanlarda öncü bir isimdi; ayrıca teorik bilgisayar bilimi ile matematik ve bilim arasındaki bağlantıyı kuran bir rol üstlendi.

• Wigderson'un başlıca başarılarından biri, rastgelelik ile hesaplama zorluğu arasındaki şaşırtıcı bağlantıyı keşfetmesiydi. Çalışmaları, rastgeleliğin verimli hesaplama için mutlaka gerekli olmadığını ortaya koydu.

• 2021'de Abel Prize'ı da kazanarak, teorik/soyut matematik ve bilgisayar bilimi alanlarındaki en yüksek onurların ikisini birden elde eden ender bir kariyere sahip oldu.

• Wigderson'un "Mathematics and Computation" adlı kitabı yakın zamanda yayımlandı ve olumlu eleştiriler alıyor.

• Araştırma sonuçlarına göre, herhangi bir önerme ispatlanabiliyorsa zero-knowledge proof da mümkündür; ayrıca sözde rastgele sayılar olasılıksal algoritmalara uygulandığında, aynı problem için verimli deterministik algoritmalar elde edilebilir. Bu, AI gibi olasılıksal hesaplama modellerinin karmaşıklığının büyük ölçüde azaltılabileceğine işaret ediyor.