Penghargaan ACM Turing 2023 dianugerahkan kepada Prof. Avi Wigderson

• Ilmu komputer teoretis membahas landasan matematis dari bidang komputasi. Bidang ini mengajukan pertanyaan seperti, "Apakah masalah ini dapat diselesaikan melalui komputasi?" dan "Jika masalah ini dapat diselesaikan dengan komputasi, berapa banyak waktu dan sumber daya yang dibutuhkan?" Selain itu, bidang ini juga mengeksplorasi cara merancang algoritma yang efisien. Semua teknologi komputasi yang memengaruhi kehidupan kita dimungkinkan oleh algoritma. Memahami prinsip algoritma yang kuat dan efisien tidak hanya memperdalam ilmu komputer, tetapi juga pemahaman kita tentang hukum alam. Ilmu komputer teoretis dikenal sebagai bidang yang menawarkan tantangan intelektual yang menarik, dan meskipun sering tidak terkait langsung dengan peningkatan aplikasi praktis komputasi, inovasi riset di bidang ini telah mendorong kemajuan di hampir semua area seperti kriptografi, biologi komputasional, desain jaringan, machine learning, dan komputasi kuantum.

• Pada dasarnya, komputer adalah sistem deterministik. Jika serangkaian instruksi algoritma diterapkan pada input tertentu, maka proses komputasinya ditentukan secara unik, dan khususnya output-nya juga ditentukan. Dengan kata lain, algoritma deterministik mengikuti pola yang dapat diprediksi. Sebaliknya, keacakan adalah ketiadaan pola yang terdefinisi dengan baik atau kemampuan untuk memprediksi peristiwa/hasil. Karena dunia tempat kita hidup tampak penuh dengan peristiwa acak (seperti sistem cuaca, fenomena biologis/kuantum, dan sebagainya), para ilmuwan komputer telah memperkuat algoritma agar dapat membuat pilihan acak selama proses komputasi demi meningkatkan efisiensinya. Faktanya, banyak masalah yang belum diketahui memiliki algoritma deterministik efisien justru telah diselesaikan secara efisien oleh algoritma probabilistik (meskipun dengan probabilitas kesalahan kecil yang dapat dikurangi secara efisien). Namun, apakah keacakan itu benar-benar esensial, atau dapat dihilangkan? Seperti apa kualitas keacakan yang dibutuhkan agar algoritma probabilistik berhasil?

• Dr. Avi Wigderson telah memimpin riset ilmu komputer teoretis selama 40 tahun dan memberikan kontribusi mendasar terhadap pemahaman tentang peran keacakan dan pseudokeacakan dalam komputasi. Para ilmuwan komputer menemukan keterkaitan yang sangat penting antara keacakan dan kesulitan komputasi (mengidentifikasi masalah alami yang tidak memiliki algoritma efisien). Dr. Wigderson bersama rekan-rekannya melakukan serangkaian penelitian yang sangat berpengaruh tentang menukar kesulitan dengan keacakan. Mereka membuktikan bahwa, di bawah asumsi komputasi standar yang dipercaya luas, semua algoritma probabilistik waktu-polinomial dapat menghilangkan keacakan secara efisien (yakni, dibuat sepenuhnya deterministik). Dengan kata lain, keacakan tidak esensial bagi komputasi efisien. Rangkaian penelitian ini merevolusi pemahaman kita tentang peran keacakan dalam komputasi dan cara kita memandang keacakan.

Kontribusi Dr. Wigderson

• "Hardness vs. Randomness" (ditulis bersama Noam Nisan): Makalah ini, di antaranya, memperkenalkan jenis baru pseudorandom generator dan membuktikan bahwa simulasi deterministik yang efisien untuk algoritma teracak dimungkinkan di bawah asumsi yang jauh lebih lemah daripada yang diketahui sebelumnya.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (ditulis bersama László Babai, Lance Fortnow, Noam Nisan): Makalah ini menggunakan "hardness amplification" untuk menunjukkan bahwa bounded-error probabilistic polynomial time (BPP) dapat disimulasikan dalam subexponential time untuk tak hingga banyak panjang input di bawah asumsi yang lebih lemah.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (ditulis bersama Russell Impagliazzo): Makalah ini memperkenalkan pseudorandom generator yang lebih kuat dengan tradeoff hardness vs randomness yang pada dasarnya optimal.

• Di luar riset terkait keacakan, Dr. Wigderson juga menunjukkan kepemimpinan intelektual di berbagai bidang lain dalam ilmu komputer teoretis, seperti multi-prover interactive proofs, kriptografi, dan kompleksitas sirkuit.

Opini GN⁺

• Riset Wigderson yang membuktikan hubungan antara keacakan dan kompleksitas komputasi dari sisi matematis memiliki makna besar dalam konteks pertemuan antara ilmu komputer dan matematika. Secara khusus, pembuktian bahwa banyak algoritma yang sebelumnya bergantung pada keacakan ternyata dapat diimplementasikan secara deterministik dengan hasil yang sama dinilai membuka cakrawala baru dalam ilmu komputer.

• Selain itu, pendekatan matematis terhadap hubungan antara efisiensi dan kesukaran juga tampaknya akan menjadi topik riset penting dalam ilmu komputer teoretis. Gagasan bahwa semakin sulit suatu masalah, justru semakin besar kemungkinan adanya algoritma yang lebih efisien untuknya merupakan wawasan yang tidak intuitif.

• Sementara itu, fakta bahwa Prof. Wigderson menekankan perpaduan matematika dan ilmu komputer demi kemajuan ilmu komputer teoretis serta berupaya membina generasi penerus juga tampak menjadi teladan yang baik bagi generasi akademik berikutnya. Khususnya, rekam jejaknya yang meraih Abel Prize di bidang matematika dan Turing Award di bidang ilmu komputer dapat disebut sebagai contoh simbolis yang menunjukkan pentingnya ilmu komputer teoretis.

[GN⁺]

Komentar Hacker News

• Avi Wigderson menerima ACM A.M. Turing Award 2023. Penghargaan ini mengakui kontribusi mendasarnya pada teori komputasi, khususnya dalam membentuk ulang pemahaman tentang peran keacakan dalam komputasi, serta kepemimpinan intelektualnya selama beberapa dekade di bidang ilmu komputer teoretis.

• Wigderson merupakan tokoh terdepan dalam bidang teori kompleksitas komputasi, algoritme dan optimisasi, keacakan dan kriptografi, komputasi paralel dan terdistribusi, kombinatorika, teori graf, dan lainnya. Ia juga berperan sebagai penghubung antara ilmu komputer teoretis dengan matematika serta sains.

• Salah satu pencapaian utama Wigderson adalah menemukan keterkaitan yang mengejutkan antara keacakan dan tingkat kesulitan komputasi. Penelitiannya menunjukkan bahwa keacakan tidak selalu diperlukan untuk komputasi yang efisien.

• Pada 2021, ia juga menerima Abel Prize, menjadikannya sosok langka yang meraih kedua penghargaan tertinggi di bidang matematika teoretis/abstrak dan ilmu komputer.

• Bukunya, "Mathematics and Computation", baru-baru ini terbit dan mendapat sambutan hangat.

• Menurut hasil penelitiannya, jika suatu pernyataan dapat dibuktikan maka zero-knowledge proof juga dimungkinkan, dan jika pseudorandomness diterapkan pada algoritme probabilistik, maka dapat diperoleh algoritme deterministik yang efisien untuk masalah yang sama. Ini mengisyaratkan bahwa kompleksitas model komputasi probabilistik seperti AI dapat sangat dikurangi.