รางวัล ACM Turing Award ปี 2023 มอบให้ศาสตราจารย์ Avi Wigderson

 (awards.acm.org)
1 คะแนน โดย GN⁺ 2024-04-12 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ACM เลือก Avi Wigderson เป็นผู้ได้รับรางวัล ACM A.M. Turing Award ปี 2023 เพื่อยกย่องผลงานที่ทำให้เกิดความเข้าใจใหม่ต่อทฤษฎีการคำนวณและบทบาทของความสุ่มในการคำนวณ
  • Wigderson เป็น Herbert H. Maass Professor แห่ง Institute for Advanced Study และเป็นบุคคลที่ขับเคลื่อน ทฤษฎีความซับซ้อนเชิงคำนวณ รวมถึงอัลกอริทึม, วิทยาการรหัสลับ, การคำนวณแบบขนานและแบบกระจาย, คอมบินาทอริกส์ และทฤษฎีกราฟอย่างกว้างขวาง
  • ผลงานสำคัญคือการวิจัย hardness for randomness ซึ่งแสดงให้เห็นว่า ภายใต้สมมติฐานเชิงคำนวณที่ได้รับความเชื่อถืออย่างกว้างขวาง อัลกอริทึมเชิงความน่าจะเป็นที่ใช้เวลาแบบพหุนามสามารถจำลองแบบกำหนดแน่นอนได้
  • บทความที่เกี่ยวข้องเสนอ ตัวสร้างเลขเทียมสุ่ม, การจำลอง BPP ด้วยเวลาแบบกึ่งเอ็กซ์โพเนนเชียล และการแลกเปลี่ยนระหว่าง hardness-vs-randomness พร้อมส่งอิทธิพลต่อหลายด้านของวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • Turing Award ได้รับการสนับสนุนจาก Google พร้อม เงินรางวัล 1 ล้านดอลลาร์ และ Wigderson ยังได้รับการยกย่องไม่เพียงจากความสำเร็จทางเทคนิค แต่ยังในฐานะเมนเทอร์ที่ชี้นำเยาวชนวิจัยรุ่นใหม่ด้วย

เบื้องหลังการได้รับรางวัล ACM Turing Award

  • ACM เลือก Avi Wigderson เป็นผู้ได้รับรางวัล ACM A.M. Turing Award ปี 2023
  • เหตุผลในการมอบรางวัลคือผลงานพื้นฐานต่อทฤษฎีการคำนวณ ความสำเร็จในการปรับโครงความเข้าใจเกี่ยวกับบทบาทของ ความสุ่ม ในการคำนวณ และภาวะผู้นำทางปัญญาตลอดหลายทศวรรษในวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • Wigderson เป็น Herbert H. Maass Professor ภาควิชาคณิตศาสตร์ของ Institute for Advanced Study ในพรินซ์ตัน รัฐนิวเจอร์ซีย์

  • สาขาหลักที่ทำงาน

    • ทฤษฎีความซับซ้อนเชิงคำนวณ
    • อัลกอริทึมและการเพิ่มประสิทธิภาพ
    • ความสุ่มและวิทยาการรหัสลับ
    • การคำนวณแบบขนานและแบบกระจาย
    • คอมบินาทอริกส์และทฤษฎีกราฟ
    • การเชื่อมโยงวิทยาการคอมพิวเตอร์เชิงทฤษฎีกับคณิตศาสตร์และวิทยาศาสตร์
    • ACM A.M. Turing Award ถูกเรียกว่า “รางวัลโนเบลแห่งวงการคอมพิวติ้ง” และมีเงินรางวัล 1 ล้านดอลลาร์ จากการสนับสนุนทางการเงินของ Google, Inc.
    • รางวัลนี้ตั้งชื่อตาม Alan M. Turing นักคณิตศาสตร์ชาวอังกฤษ ผู้วางรากฐานทางคณิตศาสตร์ของคอมพิวติ้ง

คำถามที่วิทยาการคอมพิวเตอร์เชิงทฤษฎีศึกษา

  • วิทยาการคอมพิวเตอร์เชิงทฤษฎี ว่าด้วยรากฐานทางคณิตศาสตร์ของวิทยาการคอมพิวเตอร์ และศึกษาคำถามอย่าง “ปัญหานี้แก้ได้ด้วยการคำนวณหรือไม่” และ “ถ้าแก้ได้ ต้องใช้เวลาและทรัพยากรมากเพียงใด”
  • สาขานี้ยังสำรวจหลักการออกแบบอัลกอริทึมที่มีประสิทธิภาพด้วย
  • อัลกอริทึมคือรากฐานที่ทำให้เทคโนโลยีคอมพิวติ้งที่ใช้ในชีวิตประจำวันเป็นไปได้
  • วิทยาการคอมพิวเตอร์เชิงทฤษฎียังรับมือกับความท้าทายทางปัญญาที่อาจไม่ได้ปรับปรุงการประยุกต์ใช้ในทางปฏิบัติทันที แต่ความก้าวหน้าทางการวิจัยอาจนำไปสู่การพัฒนาในหลายด้าน
    • วิทยาการรหัสลับ
    • ชีววิทยาเชิงคำนวณ
    • การออกแบบเครือข่าย
    • แมชชีนเลิร์นนิง
    • ควอนตัมคอมพิวติ้ง

เหตุใดความสุ่มจึงสำคัญในการคำนวณ

  • โดยพื้นฐานแล้วคอมพิวเตอร์เป็น ระบบกำหนดแน่นอน โดยชุดคำสั่งของอัลกอริทึมจะกำหนดการคำนวณและผลลัพธ์อย่างเป็นเอกลักษณ์สำหรับอินพุตที่กำหนด
  • ความสุ่ม หมายถึงสภาวะที่เหตุการณ์หรือผลลัพธ์ไม่มีรูปแบบชัดเจนหรือไม่สามารถคาดการณ์ได้
  • ในโลกจริงมีเหตุการณ์มากมายที่ดูเหมือนสุ่ม เช่น ระบบสภาพอากาศ ปรากฏการณ์ทางชีววิทยา และปรากฏการณ์ควอนตัม
  • นักวิทยาการคอมพิวเตอร์ได้ขยายอัลกอริทึมให้เลือกแบบสุ่มในระหว่างกระบวนการคำนวณ เพื่อเพิ่มประสิทธิภาพ
  • ปัญหาจำนวนมากที่ยังไม่พบอัลกอริทึมแบบกำหนดแน่นอนที่มีประสิทธิภาพ ก็สามารถแก้ได้อย่างมีประสิทธิภาพด้วย อัลกอริทึมเชิงความน่าจะเป็น ที่มีความน่าจะเป็นของข้อผิดพลาดต่ำ
    • ความน่าจะเป็นของข้อผิดพลาดนี้สามารถลดลงได้อย่างมีประสิทธิภาพ
  • คำถามสำคัญคือความสุ่มจำเป็นหรือไม่ สามารถกำจัดออกได้หรือไม่ และคุณภาพของความสุ่มที่จำเป็นต่อความสำเร็จของอัลกอริทึมเชิงความน่าจะเป็นคืออะไร
  • การเข้าใจพฤติกรรมของความสุ่มและความเทียมสุ่มในการคำนวณให้ดียิ่งขึ้น อาจนำไปสู่การพัฒนาอัลกอริทึมที่ดีกว่าและความเข้าใจธรรมชาติของการคำนวณเอง

ผลงานวิจัยสำคัญของ Wigderson

  • Wigderson เป็นผู้ขับเคลื่อนงานวิจัยด้านวิทยาการคอมพิวเตอร์เชิงทฤษฎีมา 40 ปี และมีผลงานพื้นฐานต่อการทำความเข้าใจบทบาทของ ความสุ่ม และ ความเทียมสุ่ม ในการคำนวณ
  • นักวิทยาการคอมพิวเตอร์ค้นพบความเชื่อมโยงสำคัญระหว่างความสุ่มกับความยากของการคำนวณ หรือการระบุปัญหาธรรมชาติที่ไม่มีอัลกอริทึมที่มีประสิทธิภาพ
  • Wigderson และผู้ร่วมวิจัยตีพิมพ์งานวิจัยทรงอิทธิพลเกี่ยวกับ hardness for randomness
  • งานวิจัยเหล่านี้แสดงให้เห็นว่า ภายใต้สมมติฐานเชิงคำนวณมาตรฐานและได้รับความเชื่อถืออย่างกว้างขวาง อัลกอริทึมเชิงความน่าจะเป็นที่ใช้เวลาแบบพหุนามทุกตัวสามารถ ทำให้เป็นแบบกำหนดแน่นอน ได้อย่างมีประสิทธิภาพ
  • ผลลัพธ์นี้แสดงให้เห็นว่าความสุ่มอาจไม่จำเป็นเสมอไปสำหรับการคำนวณที่มีประสิทธิภาพ
  • แนวทางงานวิจัยนี้เปลี่ยนบทบาทของความสุ่มในการคำนวณและวิธีคิดเกี่ยวกับความสุ่ม

  • บทความตัวแทน 3 เรื่อง

    • Hardness vs. Randomness
      • เขียนร่วมกับ Noam Nisan
      • นำเสนอ ตัวสร้างเลขเทียมสุ่ม ประเภทใหม่
      • พิสูจน์ว่าการจำลองอัลกอริทึมแบบสุ่มให้เป็นแบบกำหนดแน่นอนอย่างมีประสิทธิภาพสามารถทำได้ภายใต้สมมติฐานที่อ่อนกว่าก่อนหน้านี้มาก
    • BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs
      • เขียนร่วมกับ László Babai, Lance Fortnow และ Noam Nisan
      • ใช้ hardness amplification
      • แสดงให้เห็นว่า bounded-error probabilistic polynomial time หรือ BPP สามารถถูกจำลองด้วยเวลาแบบกึ่งเอ็กซ์โพเนนเชียลสำหรับความยาวอินพุตจำนวนอนันต์ ภายใต้สมมติฐานที่อ่อนกว่า
    • P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
      • เขียนร่วมกับ Russell Impagliazzo
      • นำเสนอ ตัวสร้างเลขเทียมสุ่ม ที่แข็งแกร่งยิ่งขึ้น
      • เสนอการแลกเปลี่ยนแบบ hardness-vs-randomness ที่เกือบเหมาะที่สุด

ขอบเขตอิทธิพลและผลงานเพิ่มเติม

  • บทความสามเรื่องของ Wigderson ส่งอิทธิพลต่อหลายสาขาของวิทยาการคอมพิวเตอร์เชิงทฤษฎี นอกเหนือจากด้านความสุ่มและการทำให้เป็นแบบกำหนดแน่นอน
  • แนวคิดจากบทความเหล่านี้ถูกนำไปใช้ในบทความทรงอิทธิพลของนักวิจัยสำคัญหลายคนในเวลาต่อมา
  • ในบทความร่วมกับ Omer Reingold, Salil Vadhan และ Michael Capalbo ได้นำเสนอการสร้างเชิงคอมบินาทอริกส์ที่มีประสิทธิภาพครั้งแรกของ expander graph
    • expander graph คือกราฟเบาบางที่มีคุณสมบัติการเชื่อมต่ออย่างแข็งแกร่ง
    • มีการประยุกต์ใช้สำคัญทั้งในคณิตศาสตร์และวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • นอกจากความสุ่มแล้ว Wigderson ยังแสดงภาวะผู้นำทางปัญญาในสาขาต่อไปนี้
    • multi-prover interactive proofs
    • วิทยาการรหัสลับ
    • ความซับซ้อนของวงจร

การเป็นเมนเทอร์และการประเมิน

  • Wigderson ได้รับการยอมรับไม่เพียงจากผลงานทางเทคนิคที่บุกเบิกเท่านั้น แต่ยังเป็น เมนเทอร์ และเพื่อนร่วมงานที่เป็นที่เคารพ ซึ่งได้ชี้แนะนักวิจัยรุ่นใหม่จำนวนมาก
  • ความรู้กว้างขวาง ความสามารถทางเทคนิค ความเป็นกันเอง ความกระตือรือร้น และความเอื้อเฟื้อของเขาถูกมองว่าเป็นปัจจัยที่ดึงดูดนักวิจัยรุ่นใหม่ที่ยอดเยี่ยมให้เดินตามเส้นทางอาชีพในวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • Yannis Ioannidis ประธาน ACM ระบุว่า Wigderson ยังได้รับ Abel Prize ซึ่งถือเป็นหนึ่งในเกียรติยศสูงสุดสำหรับผลงานตลอดชีวิตในสาขาคณิตศาสตร์
  • Ioannidis ประเมินว่าคณิตศาสตร์คือรากฐานของวิทยาการคอมพิวเตอร์ และผลงานของ Wigderson ได้เชื่อมโยงสาขาย่อยต่าง ๆ ของคณิตศาสตร์เข้ากับวิทยาการคอมพิวเตอร์เชิงทฤษฎี
  • Jeff Dean, Senior Vice President ของ Google กล่าวว่า งานวิจัยของ Wigderson เกี่ยวกับความสุ่มและหัวข้ออื่น ๆ ได้กำหนดวาระของวิทยาการคอมพิวเตอร์เชิงทฤษฎีตลอด 30 ปีที่ผ่านมา
  • Dean ยังเน้นว่า Wigderson เป็นเมนเทอร์ที่สร้างแนวคิดและทิศทางการวิจัย พร้อมจูงใจให้นักวิจัยรุ่นใหม่ทำงานตามทิศทางเหล่านั้น

Turing Award และบทความสำคัญเพิ่มเติมของ Wigderson

  • A.M. Turing Award ยกย่องนักวิทยาการคอมพิวเตอร์และวิศวกรผู้สร้างระบบและรากฐานเชิงทฤษฎีที่ขับเคลื่อนอุตสาหกรรมเทคโนโลยีสารสนเทศมาตั้งแต่เริ่มในปี 1966
  • ประวัติรางวัลของ Wigderson รวมถึง
    • Abel Prize
    • IMU Abacus Medal ซึ่งเดิมชื่อ Nevanlinna Prize
    • Donald E. Knuth Prize
    • Edsger W. Dijkstra Prize in Distributed Computing
    • Gödel Prize
  • Wigderson เป็น ACM Fellow และเป็นสมาชิกของ U.S. National Academy of Sciences และ American Academy of Arts and Sciences

  • บทความสำคัญเพิ่มเติม

    • In Search of an Easy Witness: Exponential Time vs Probabilistic Polynomial Time
      • เขียนร่วมกับ Russell Impagliazzo และ Valentine Kabanets
      • วางผลลัพธ์หลายประการเกี่ยวกับความสัมพันธ์ด้านความซับซ้อนของคลาสความซับซ้อนแบบเวลาเอ็กซ์โพเนนเชียลและเวลาแบบพหุนามเชิงความน่าจะเป็น
    • Randomness vs. Time: De-Randomization Under a Uniform Assumption
      • เขียนร่วมกับ Russell Impagliazzo
      • พิสูจน์ว่า หาก BPP≠EXP ปัญหาทั้งหมดใน BPP สามารถแก้ได้ด้วยเวลาแบบกึ่งเอ็กซ์โพเนนเชียลเชิงกำหนดแน่นอนบนอินพุตเกือบทั้งหมด
    • Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
      • เขียนร่วมกับ Michael Ben-Or, Shafi Goldwasser และ Joe Kilian
      • พิสูจน์ว่าภาษาทุกภาษาใน NP มีระบบพิสูจน์แบบศูนย์ความรู้ที่สมบูรณ์
    • Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems
      • เขียนร่วมกับ Oded Goldreich และ Silvio Micali
      • แสดงให้เห็นว่าภาษาทุกภาษาใน NP มีการพิสูจน์แบบศูนย์ความรู้ โดยอาศัยสมมติฐานว่ามีฟังก์ชันเข้ารหัสที่ปลอดภัยอยู่จริง หรือใช้วิธีการทางกายภาพเพื่อซ่อนข้อมูล

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-04-12
ความคิดเห็นบน Hacker News

  • บทความสำคัญสองฉบับของ Wigderson ที่กล่าวถึงในประกาศ เขียนร่วมกับ Noam Nisan หนึ่งในอาจารย์ผู้สร้างคอร์สออนไลน์ชื่อดัง From Nand to Tetris

    • ศาสตราจารย์ Nisan ก็เป็นบุคคลที่ยอดเยี่ยมเช่นกัน หลังจากสร้างผลงานระดับแนวหน้าใน ทฤษฎีการคำนวณ แล้ว เขายังมีอิทธิพลอย่างมากในสาขาที่ค่อนข้างต่างออกไปอย่าง ทฤษฎีเกมเชิงอัลกอริทึม
      เป็นเรื่องดีที่คนคนหนึ่งสามารถสร้างความสำเร็จได้หลากหลายขนาดนี้ และระบบที่เปิดให้มีความยืดหยุ่นแบบนั้นก็น่าประทับใจเช่นกัน
    • มีหนังสือด้วย เพิ่งออก ฉบับพิมพ์ครั้งที่ 2 เมื่อไม่นานมานี้

  • Quanta ก็มีบทความดี ๆ เช่นกัน: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    ท่าทางที่ให้ Wigderson โพสมีหลากหลายจนน่าสนุก ดูเก้กังมาก เหมือนแนวว่า “เอาละ นั่งบนเก้าอี้ตัวนี้แล้วทอดสายตามองออกไปนอกหน้าต่างอย่างลึกซึ้งนะครับ”

    • ส่วนที่บอกว่า “ประสิทธิผลอันไม่สมเหตุสมผลของความสุ่ม” ทำให้ Wigderson หันมาคิดถึงแก่นแท้ของความสุ่มเองนั้นน่าสนใจ
      เท่าที่เข้าใจ complexity class จัดการกับประสิทธิภาพในกรณีเลวร้ายที่สุด เลยอยากรู้คร่าว ๆ ว่าแม้จะมี ตัวสร้างเลขสุ่มเทียม ที่ดีและอัลกอริทึมแบบ randomized ที่ดี เขาพิสูจน์ได้อย่างไรว่าชุดผสมใด ๆ ของ RNG + seed + problem instance จะไม่ใช้เวลาแบบเลขชี้กำลัง
    • ถ้าดูข้อความแก้ไข เดิมทีบทความบอกว่า Wigderson เรียนที่ University of Haifa แต่จริง ๆ แล้วเขาจบจาก Technion ในไฮฟา ประเทศอิสราเอล
      สงสัยว่านักข่าวสับสนเรื่องนี้ได้อย่างไร
    • ท่า “นั่งบนเก้าอี้มองออกไปนอกหน้าต่าง” ดูเหมือนท่าแบบ Martin Scorsese หรือ Sopranos เป็นฉากเหมือนแก๊งสเตอร์แก่ในบ้านพักคนชรา

  • Scott Aaronson เขียนไว้ว่าเลกเชอร์ครั้งหนึ่งของ Avi Wigderson ส่งผลต่อเส้นทางอาชีพของเขาอย่างไร: https://scottaaronson.blog/?p=2925

  • มีข้อมูลเพิ่มเติมใน “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness”: [1] และฉบับเก็บถาวร [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • ถ้าจะตามงานวิจัยของ Wigderson ด้าน การแลกเปลี่ยนระหว่างความยากกับความสุ่ม ควรเริ่มจากตรงไหนดี
    ปกติไม่ค่อยมีกรณีที่ไม่เคยได้ยินชื่อผู้ชนะรางวัล Turing เลย แต่คนนี้อยู่นอกสายตาโดยสิ้นเชิง

    • ดูหนังสือของเขาได้: https://www.math.ias.edu/avi/book
    • สงสัยว่า “สมมติฐานด้านการคำนวณที่เป็นมาตรฐานและเชื่อกันอย่างแพร่หลาย” คืออะไร
      เดาว่าอาจหมายถึงการประมาณเชิงความน่าจะเป็นสำหรับ ปัญหา NP-complete ก็ยังไม่ใช่เวลาเชิงพหุนาม หรือไม่ก็สับสนว่าเวอร์ชันที่ตัดความสุ่มออกแล้วยังถือเป็นอัลกอริทึมประมาณค่าอยู่หรือเปล่า

  • เพิ่งหยิบหนังสือของ Wigderson มาอ่าน และจนถึงตอนนี้ก็ชอบ: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • ถ้าเป็นเพื่อการวิจัยส่วนตัวและการศึกษา สามารถดู ร่างสุดท้าย ของหนังสือได้ที่นี่: https://www.math.ias.edu/avi/book
    • ได้ดูหนังสือแล้ว ระดับดูเหมาะกับนักศึกษาบัณฑิตศึกษาหรือนักศึกษาปริญญาตรีชั้นสูงมากกว่า
      อยากทราบว่ามีหนังสือที่ปูพื้น หัวข้อด้านการคำนวณ ในระดับพื้นฐานกว่านี้สำหรับคนที่พื้นฐานปริญญาตรีด้านวิทยาการคอมพิวเตอร์/คณิตศาสตร์เริ่มขึ้นสนิมบ้างไหม

  • ในบทความที่เกี่ยวข้องมีประโยคนี้: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “ถ้าข้อความใดพิสูจน์ได้ มันก็มี zero-knowledge proof ด้วย” อ่านแล้วเหมือนหัวจะระเบิด
    อีกประโยคที่ว่า “ถ้าใส่บิตสุ่มเทียมเข้าไปในอัลกอริทึมเชิงความน่าจะเป็นแทนบิตสุ่ม ก็จะได้อัลกอริทึมเชิงกำหนดที่มีประสิทธิภาพสำหรับปัญหาเดียวกัน” ก็น่าทึ่งจนแทบไม่น่าเชื่อ
    AI ก็เป็นการคำนวณเชิงความน่าจะเป็นเหมือนกัน ดังนั้นถ้าผมอ่านถูก นี่หมายความว่าสามารถลดความซับซ้อนของโมเดลปัจจุบันลงได้หลายหลักหรือเปล่า ถ้าเป็นความเข้าใจผิดของมือใหม่ก็อยากให้ใครช่วยดึงกลับมาที

    • ไม่แน่ใจว่าหมายถึงอะไรแน่ แต่ไม่ใช่ความหมายแบบนั้นอย่างน้อย AI ใช้ เลขสุ่มเทียม อยู่แล้วและเป็น deterministic
      มีข้อยกเว้นอย่างชิปเร่ง AI แบบแปลก ๆ ที่ใช้การคำนวณแบบแอนะล็อกเพื่อเพิ่มประสิทธิภาพ
    • น่าเสียดาย แต่ไม่ใช่ อย่างแรก ผลลัพธ์นั้นใช้กับ ปัญหาการตัดสินใจ ไม่ใช่ปัญหาการค้นหา
      อย่างที่สอง อัลกอริทึมเชิงกำหนดที่สร้างขึ้นมีประสิทธิภาพน้อยกว่าอัลกอริทึมแบบ randomized มาก เพียงแต่อยู่ใน complexity class เดียวกันภายใต้สมมติฐานที่อ่อนเท่านั้น

  • ชอบส่วนนี้ในบทความ: “แรงจูงใจไม่ใช่การประยุกต์ใช้ แต่ผมรู้ว่างานวิจัยพื้นฐานก็อาจพบการใช้งานได้ ลองนึกถึง Alan Turing เขาเขียนบทความคณิตศาสตร์เชิงตรรกะเกี่ยวกับ Entscheidungsproblem ในวารสารที่ไม่ค่อยมีใครรู้จัก แรงจูงใจไม่ใช่การประยุกต์ใช้”
    คล้ายเกร็ดเรื่องจานของ Feynman เริ่มจากการตอบสนองแบบเล่น ๆ ต่อสิ่งที่เห็นในโรงอาหารมหาวิทยาลัย แล้วสุดท้ายนำไปสู่ รางวัล Nobel
    ถ้าขยายประเด็นให้กว้างขึ้น วงการวิชาการสมัยใหม่กำลังมุ่งไปในทางที่กดทับ การแสวงหาความรู้จากความใคร่รู้ แบบนี้

  • ตามข้อมูลของ ACM Avi Wigderson ได้รับเลือกเป็นผู้ชนะรางวัล 2023 ACM A.M. Turing Award จากผลงานพื้นฐานด้าน ทฤษฎีการคำนวณ รวมถึงการปรับเปลี่ยนความเข้าใจเกี่ยวกับบทบาทของความสุ่มในการคำนวณ และจากภาวะผู้นำทางปัญญาตลอดหลายทศวรรษในวิทยาการคอมพิวเตอร์เชิงทฤษฎี
    Wigderson เป็น Herbert H. Maass Professor ในคณะคณิตศาสตร์ของ Institute for Advanced Study ที่พรินซ์ตัน รัฐนิวเจอร์ซีย์ และเป็นบุคคลสำคัญในด้านทฤษฎีความซับซ้อนเชิงคำนวณ อัลกอริทึมและการหาค่าเหมาะที่สุด ความสุ่มและวิทยาการเข้ารหัสลับ การคำนวณแบบขนานและแบบกระจาย คอมบินาทอริกส์ ทฤษฎีกราฟ รวมถึงความเชื่อมโยงระหว่างวิทยาการคอมพิวเตอร์เชิงทฤษฎีกับคณิตศาสตร์และวิทยาศาสตร์
    เขายังได้รับ รางวัล Abel ในปี 2021 ด้วย จึงเป็นชุดเกียรติยศที่ค่อนข้างพิเศษ คือได้รับรางวัลสูงสุดทั้งในคณิตศาสตร์เชิงทฤษฎี/นามธรรมและวิทยาการคอมพิวเตอร์

    • ส่วนซ้อนทับระหว่างวิทยาการคอมพิวเตอร์เชิงทฤษฎีกับคณิตศาสตร์นั้นใหญ่กว่าที่คนส่วนใหญ่รู้มาก
      ตัวอย่างง่าย ๆ คือถ้าดูรายวิชาวิทยาการคอมพิวเตอร์เชิงทฤษฎีของ MIT https://catalog.mit.edu/subjects/6/ จะเห็นว่ามีกี่วิชาที่เปิดสอนร่วมกับ course 18 ซึ่งเป็นคณิตศาสตร์
    • ถ้าพูดอย่างเคร่งครัด เกียรติยศสูงสุดของคณิตศาสตร์คือ Fields Medal
      แน่นอน ผมก็ไม่ได้อยู่ในฐานะที่จะไปว่าอะไรได้

  • อยากได้คำแนะนำแหล่งเรียนรู้หัวข้อ ความน่าจะเป็น/ความสุ่มและการคำนวณ ตั้งแต่ระดับเป็นมิตรกับผู้เริ่มต้นไปจนถึงขั้นสูง
    ค้น Google แล้วเจอ “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” ของ Eli Upfal และ Michael Mitzenmacher แต่หาเล่ม/บทความ/วิดีโอสำหรับผู้เริ่มต้นหรือระดับปูพื้นไม่ค่อยเจอ