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

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

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

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

คุณูปการของ ดร. Wigderson

• "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) สามารถถูกจำลองได้ใน subexponential time สำหรับความยาวอินพุตจำนวนอนันต์ภายใต้สมมติฐานที่อ่อนกว่า

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (เขียนร่วมกับ Russell Impagliazzo): งานชิ้นนี้นำเสนอเครื่องกำเนิดความสุ่มเทียมที่ทรงพลังยิ่งขึ้น ซึ่งมี hardness vs randomness tradeoff ที่โดยสาระสำคัญแล้วเหมาะที่สุด

• นอกเหนือจากงานวิจัยที่เกี่ยวข้องกับความสุ่มแล้ว ดร. Wigderson ยังได้แสดงบทบาทผู้นำทางปัญญาในอีกหลายด้านของวิทยาการคอมพิวเตอร์เชิงทฤษฎี เช่น interactive proofs แบบหลายผู้พิสูจน์ วิทยาการเข้ารหัสลับ และความซับซ้อนของวงจร

ความเห็นของ GN⁺

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

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

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

[GN⁺]

ความคิดเห็นจาก Hacker News

• Avi Wigderson ได้รับรางวัล ACM A.M. Turing Award ประจำปี 2023 จากผลงานบุกเบิกด้านทฤษฎีการคำนวณ โดยเฉพาะการปรับกรอบความเข้าใจใหม่เกี่ยวกับบทบาทของความสุ่มในการคำนวณ และการเป็นผู้นำทางความคิดในสาขาวิทยาการคอมพิวเตอร์เชิงทฤษฎีมายาวนานหลายทศวรรษ

• Wigderson เป็นบุคคลชั้นนำในสาขาต่าง ๆ เช่น ทฤษฎีความซับซ้อนเชิงคำนวณ, อัลกอริทึมและการหาค่าเหมาะที่สุด, ความสุ่มและวิทยาการเข้ารหัสลับ, การประมวลผลแบบขนานและแบบกระจาย, คอมบินาทอริกส์ และทฤษฎีกราฟ อีกทั้งยังทำหน้าที่เชื่อมโยงระหว่างวิทยาการคอมพิวเตอร์เชิงทฤษฎีกับคณิตศาสตร์และวิทยาศาสตร์อีกด้วย

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

• ในปี 2021 เขายังได้รับ Abel Prize ทำให้มีประวัติที่โดดเด่นไม่เหมือนใครจากการคว้าสองเกียรติยศสูงสุดในสาขาคณิตศาสตร์เชิงทฤษฎี/นามธรรมและวิทยาการคอมพิวเตอร์

• หนังสือของ Wigderson ชื่อ "Mathematics and Computation" เพิ่งตีพิมพ์ออกมาไม่นานและได้รับเสียงชื่นชมอย่างมาก

• ตามผลการวิจัยของเขา หากข้อความใดสามารถพิสูจน์ได้ ก็สามารถมี zero-knowledge proof ได้เช่นกัน และหากนำ pseudorandomness ไปใช้กับอัลกอริทึมเชิงความน่าจะเป็น ก็อาจได้อัลกอริทึมเชิงกำหนดที่มีประสิทธิภาพสำหรับปัญหาเดียวกัน ซึ่งชี้ให้เห็นว่าสามารถลดความซับซ้อนของโมเดลการคำนวณเชิงความน่าจะเป็นอย่าง AI ลงได้อย่างมาก