ACM Turing Award 2023 Dianugerahkan kepada Profesor Avi Wigderson

 (awards.acm.org)
1 poin oleh GN⁺ 2024-04-12 | 1 komentar | Bagikan ke WhatsApp
  • ACM memilih Avi Wigderson sebagai penerima ACM A.M. Turing Award 2023, mengakui jasanya dalam membentuk pemahaman baru tentang teori komputasi dan peran keacakan dalam komputasi
  • Wigderson adalah Herbert H. Maass Professor di Institute for Advanced Study, dan merupakan tokoh yang memimpin secara luas bidang teori kompleksitas komputasi, algoritme, kriptografi, komputasi paralel dan terdistribusi, kombinatorika, serta teori graf
  • Kontribusi utamanya adalah penelitian hardness for randomness, yang menunjukkan bahwa di bawah asumsi komputasi yang dipercaya luas, algoritme probabilistik waktu polinomial dapat disimulasikan secara deterministik
  • Makalah-makalah terkait memperkenalkan pseudorandom generator, simulasi waktu subeksponensial untuk BPP, serta trade-off hardness-vs-randomness, dan memengaruhi berbagai bidang ilmu komputer teoretis
  • Turing Award, yang didukung Google, memberikan hadiah 1 juta dolar AS, dan Wigderson dinilai bukan hanya atas capaian teknisnya, tetapi juga sebagai mentor yang membimbing peneliti muda

Latar belakang penerimaan ACM Turing Award

  • ACM memilih Avi Wigderson sebagai penerima ACM A.M. Turing Award 2023
  • Alasan penghargaan ini adalah kontribusi fundamentalnya pada teori komputasi, pencapaiannya dalam membentuk ulang pemahaman tentang peran keacakan dalam komputasi, serta kepemimpinan intelektualnya selama puluhan tahun dalam ilmu komputer teoretis
  • Wigderson adalah Herbert H. Maass Professor di School of Mathematics, Institute for Advanced Study, Princeton, New Jersey

  • Bidang kegiatan utama

    • Teori kompleksitas komputasi
    • Algoritme dan optimisasi
    • Keacakan dan kriptografi
    • Komputasi paralel dan terdistribusi
    • Kombinatorika dan teori graf
    • Keterkaitan ilmu komputer teoretis dengan matematika dan sains
    • ACM A.M. Turing Award disebut sebagai “Nobel untuk komputasi”, dan menyediakan hadiah 1 juta dolar AS dengan dukungan finansial dari Google, Inc.
    • Penghargaan ini dinamai menurut matematikawan Inggris Alan M. Turing, yang membangun fondasi matematis komputasi

Pertanyaan yang dibahas ilmu komputer teoretis

  • Ilmu komputer teoretis membahas fondasi matematis ilmu komputer, dan menelaah pertanyaan seperti “apakah masalah ini dapat diselesaikan dengan komputasi” dan “jika bisa diselesaikan, berapa banyak waktu dan sumber daya yang dibutuhkan”
  • Bidang ini juga mengeksplorasi prinsip-prinsip perancangan algoritme yang efisien
  • Algoritme adalah fondasi yang memungkinkan teknologi komputasi yang digunakan sehari-hari
  • Ilmu komputer teoretis juga menangani tantangan intelektual yang tidak langsung meningkatkan aplikasi praktis, tetapi terobosan risetnya dapat mendorong kemajuan di berbagai bidang
    • Kriptografi
    • Biologi komputasional
    • Desain jaringan
    • Machine learning
    • Komputasi kuantum

Mengapa keacakan penting dalam komputasi

  • Komputer pada dasarnya adalah sistem deterministik, dan untuk input tertentu, himpunan instruksi sebuah algoritme menentukan komputasi dan output secara unik
  • Keacakan berarti keadaan ketika tidak ada pola yang jelas atau prediktabilitas dalam peristiwa maupun hasil
  • Di dunia nyata ada banyak peristiwa yang tampak acak, seperti sistem cuaca, fenomena biologis, dan fenomena kuantum
  • Ilmuwan komputer telah memperluas algoritme agar dapat membuat pilihan acak selama proses komputasi demi meningkatkan efisiensi
  • Banyak masalah yang sebelumnya tidak memiliki algoritme deterministik efisien yang diketahui juga dapat diselesaikan secara efisien dengan algoritme probabilistik yang memiliki probabilitas kesalahan kecil
    • Probabilitas kesalahan ini dapat dikurangi secara efisien
  • Pertanyaan utamanya adalah apakah keacakan itu esensial, apakah dapat dihilangkan, dan kualitas keacakan seperti apa yang dibutuhkan agar algoritme probabilistik berhasil
  • Pemahaman yang lebih baik tentang cara kerja keacakan dan pseudo-keacakan dalam komputasi dapat mengarah pada pengembangan algoritme yang lebih baik serta pemahaman tentang hakikat komputasi itu sendiri

Kontribusi riset utama Wigderson

  • Selama 40 tahun, Wigderson telah memimpin riset ilmu komputer teoretis dan memberikan kontribusi fundamental dalam memahami peran keacakan dan pseudo-keacakan dalam komputasi
  • Ilmuwan komputer menemukan hubungan penting antara keacakan dan kesulitan komputasi, yaitu upaya mengidentifikasi masalah alami yang tidak memiliki algoritme efisien
  • Wigderson dan para kolaboratornya menerbitkan sejumlah penelitian berpengaruh tentang hardness for randomness
  • Penelitian-penelitian ini menunjukkan bahwa di bawah asumsi komputasi standar yang dipercaya luas, semua algoritme probabilistik waktu polinomial dapat diderandomisasi secara efisien
  • Hasil ini menunjukkan bahwa keacakan mungkin tidak selalu diperlukan untuk komputasi yang efisien
  • Alur penelitian tersebut mengubah cara memandang peran keacakan dalam komputasi dan cara berpikir tentang keacakan

  • 3 makalah representatif

Cakupan pengaruh dan pencapaian tambahan

  • Tiga makalah Wigderson memengaruhi berbagai bidang ilmu komputer teoretis, melampaui ranah keacakan dan derandomisasi
  • Ide-ide dalam makalah-makalah ini kemudian digunakan dalam makalah berpengaruh oleh sejumlah peneliti besar
  • Dalam makalah bersama Omer Reingold, Salil Vadhan, dan Michael Capalbo, ia menyajikan konstruksi kombinatorial efisien pertama untuk expander graph
    • Expander graph adalah graf jarang dengan sifat keterhubungan yang kuat
    • Memiliki aplikasi penting baik dalam matematika maupun ilmu komputer teoretis
  • Selain keacakan, Wigderson juga menunjukkan kepemimpinan intelektual di bidang-bidang berikut
    • multi-prover interactive proofs
    • Kriptografi
    • Kompleksitas sirkuit

Mentoring dan penilaian

  • Wigderson diakui bukan hanya atas kontribusi teknis yang terobosan, tetapi juga sebagai mentor dan kolega yang dihormati yang membimbing banyak peneliti muda
  • Pengetahuan yang luas, kemampuan teknis, sikap bersahabat, antusiasme, dan kemurahan hatinya disebut sebagai faktor yang mendorong peneliti muda berbakat untuk menekuni karier dalam ilmu komputer teoretis
  • Presiden ACM Yannis Ioannidis menyatakan bahwa Wigderson juga menerima Abel Prize, yang dianggap sebagai salah satu penghargaan paling penting untuk pencapaian seumur hidup di bidang matematika
  • Ioannidis menilai bahwa matematika adalah fondasi ilmu komputer, dan karya Wigderson menghubungkan berbagai subbidang matematika dengan ilmu komputer teoretis
  • Senior Vice President Google Jeff Dean menyatakan bahwa riset Wigderson tentang keacakan dan topik-topik lain telah membentuk agenda ilmu komputer teoretis selama 30 tahun terakhir
  • Dean juga menekankan bahwa Wigderson adalah mentor yang menciptakan gagasan dan arah riset, serta memotivasi peneliti muda untuk berkarya di arah tersebut

Turing Award dan makalah penting tambahan Wigderson

Bacaan terkait

1 komentar

 
GN⁺ 2024-04-12
Komentar Hacker News

  • Dua makalah utama Wigderson yang disebut dalam pengumuman ditulis bersama Noam Nisan, salah satu profesor yang membuat kuliah online terkenal From Nand to Tetris

    • Profesor Nisan juga sosok yang luar biasa. Setelah menghasilkan pencapaian kelas satu di teori komputasi, ia juga meninggalkan pengaruh besar di bidang yang cukup berbeda, yaitu teori permainan algoritmik
      Menarik melihat satu orang bisa mencapai prestasi yang begitu beragam, dan sistem yang memungkinkan fleksibilitas seperti itu juga mengesankan
    • Ada juga bukunya. Edisi ke-2 baru terbit belum lama ini

  • Ada juga artikel bagus dari Quanta: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Seru karena pose yang diminta dari Wigderson bermacam-macam. Terlihat sangat canggung. Rasanya seperti, “Oke, duduk di kursi ini lalu tatap ke luar jendela dengan penuh makna”

    • Bagian bahwa “efektivitas tak masuk akal dari keacakan” membuat Wigderson memikirkan hakikat keacakan itu sendiri terasa menarik
      Selama ini saya memahami kelas kompleksitas sebagai sesuatu yang membahas performa pada kasus terburuk, jadi saya ingin tahu secara garis besar bagaimana bisa dibuktikan bahwa bahkan dengan generator pseudorandom yang bagus dan algoritme teracak yang bagus, tidak ada kombinasi RNG + seed + problem instance yang akan memakan waktu eksponensial
    • Jika melihat koreksinya, artikel aslinya menyebut Wigderson kuliah di University of Haifa, tetapi sebenarnya ia lulus dari Technion di Haifa, Israel
      Saya penasaran bagaimana wartawannya bisa tertukar soal ini
    • Pose “duduk di kursi sambil melihat ke luar jendela” terasa seperti pose ala Martin Scorsese atau Sopranos. Seperti adegan gangster tua di panti jompo

  • Ada tulisan Scott Aaronson tentang bagaimana salah satu kuliah Avi Wigderson memengaruhi arah kariernya: https://scottaaronson.blog/?p=2925

  • Ada info tambahan di “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness”: [1] dan versi arsip [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Saya penasaran dari mana sebaiknya mulai jika ingin mengejar topik trade-off antara hardness dan randomness dalam penelitian Wigderson
    Jarang sekali ada peraih Turing Award yang belum pernah saya dengar sama sekali, tapi orang ini benar-benar di luar radar saya

    • Tinggal lihat bukunya: https://www.math.ias.edu/avi/book
    • Saya penasaran apa yang dimaksud dengan “asumsi komputasi standar yang dipercaya luas”
      Mungkin maksudnya bahkan aproksimasi probabilistik untuk masalah NP-complete tidak bisa dilakukan dalam waktu polinomial, atau mungkin saya bingung apakah versi yang keacakannya dihilangkan tetap merupakan algoritme aproksimasi

  • Saya baru mulai membaca buku Wigderson dan sejauh ini saya suka: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Untuk riset pribadi dan tujuan pengajaran, draf final bukunya bisa dibaca di sini: https://www.math.ias.edu/avi/book
    • Saya melihat bukunya dan rasanya levelnya lebih cocok untuk mahasiswa pascasarjana atau mahasiswa S1 tingkat lanjut
      Saya penasaran apakah ada yang bisa merekomendasikan buku yang membahas topik komputasi lebih mendasar bagi orang yang latar belakang S1 ilmu komputer/matematikanya sudah agak berkarat

  • Ada kalimat ini di artikel terkait: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “Jika suatu pernyataan bisa dibuktikan, maka ia juga punya zero-knowledge proof” benar-benar terasa bikin kepala meledak
    Lalu pernyataan bahwa “jika bit acak dalam algoritme probabilistik diganti dengan bit pseudorandom, hasilnya menjadi algoritme deterministik yang efisien untuk masalah yang sama” juga terasa luar biasa
    AI juga merupakan komputasi probabilistik, jadi kalau saya membacanya dengan benar, bukankah itu berarti kompleksitas model saat ini bisa dikurangi beberapa orde besaran? Kalau ini salah paham dari pemula, saya harap ada yang meluruskannya

    • Saya tidak tahu persis maksud kalimat itu, tetapi setidaknya bukan itu artinya. AI sudah memakai pseudorandomness dan sudah deterministik
      Ada pengecualian seperti chip akselerator AI aneh yang memakai komputasi analog untuk meningkatkan efisiensi
    • Sayangnya tidak. Pertama, hasil itu berlaku untuk masalah keputusan, bukan masalah pencarian
      Kedua, algoritme deterministik yang dihasilkan jauh kurang efisien daripada algoritme teracaknya. Hanya saja, di bawah asumsi yang lemah, ia tetap berada di kelas kompleksitas yang sama

  • Saya suka bagian artikel ini: “Aplikasi bukan motivasinya, tetapi saya tahu bahkan riset fundamental pun bisa menemukan kegunaan. Pikirkan Alan Turing. Ia menulis makalah matematika logika tentang Entscheidungsproblem di jurnal yang tidak terkenal. Aplikasi bukan motivasinya”
    Mirip dengan kisah piring Feynman. Dimulai dari reaksinya yang santai terhadap sesuatu yang ia lihat di kafetaria kampus, lalu akhirnya berujung pada Hadiah Nobel
    Jika diperluas, intinya adalah bahwa dunia akademik modern justru bergerak ke arah yang menekan penyelidikan berbasis rasa ingin tahu seperti ini

  • Menurut ACM, Avi Wigderson dipilih sebagai penerima 2023 ACM A.M. Turing Award atas kontribusi mendasarnya pada teori komputasi, termasuk membentuk ulang pemahaman tentang peran keacakan dalam komputasi, serta menunjukkan kepemimpinan intelektual selama puluhan tahun dalam ilmu komputer teoretis
    Wigderson adalah Herbert H. Maass Professor di School of Mathematics, Institute for Advanced Study, Princeton, New Jersey, dan telah menjadi tokoh kunci dalam teori kompleksitas komputasi, algoritme dan optimisasi, keacakan dan kriptografi, komputasi paralel dan terdistribusi, kombinatorika, teori graf, serta hubungan antara ilmu komputer teoretis dengan matematika dan sains
    Ia juga menerima Abel Prize pada 2021, sehingga menjadi kombinasi yang cukup unik: meraih penghargaan tertinggi di matematika teoretis/abstrak dan ilmu komputer sekaligus

    • Tumpang tindih antara ilmu komputer teoretis dan matematika jauh lebih besar daripada yang disadari kebanyakan orang
      Sebagai contoh sederhana, jika melihat daftar mata kuliah ilmu komputer teoretis MIT https://catalog.mit.edu/subjects/6/, bisa dilihat betapa banyak mata kuliah yang dibuka bersama dengan course 18, yaitu matematika
    • Secara teknis, penghargaan tertinggi di matematika adalah Fields Medal
      Tentu saja saya juga bukan dalam posisi untuk banyak bicara soal itu

  • Saya ingin rekomendasi materi belajar bertema probabilitas/keacakan dan komputasi, dari yang ramah pemula sampai tingkat lanjut
    Google menampilkan “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” karya Eli Upfal dan Michael Mitzenmacher, tetapi saya sulit menemukan buku, tulisan, atau video yang benar-benar cocok untuk tingkat awal/pengantar