Giải ACM Turing năm 2023 được trao cho Giáo sư Avi Wigderson

 (awards.acm.org)
1 điểm bởi GN⁺ 2024-04-12 | 1 bình luận | Chia sẻ qua WhatsApp
  • ACM đã chọn Avi Wigderson là người nhận giải ACM A.M. Turing Award 2023, ghi nhận công lao giúp hình thành cách hiểu mới về lý thuyết tính toán và vai trò của tính ngẫu nhiên trong tính toán
  • Wigderson là Herbert H. Maass Professor tại Institute for Advanced Study, một nhân vật có ảnh hưởng sâu rộng trong lý thuyết độ phức tạp tính toán cùng các lĩnh vực thuật toán, mật mã học, tính toán song song·phân tán, tổ hợp học và lý thuyết đồ thị
  • Thành tựu cốt lõi là nghiên cứu về hardness for randomness, cho thấy dưới các giả định tính toán được tin tưởng rộng rãi, có thể mô phỏng các thuật toán thời gian đa thức ngẫu nhiên theo cách tất định
  • Các bài báo liên quan đã đề xuất bộ sinh số giả ngẫu nhiên, mô phỏng BPP trong thời gian dưới hàm mũ, và sự đánh đổi hardness-vs-randomness, ảnh hưởng đến nhiều lĩnh vực của khoa học máy tính lý thuyết
  • Turing Award đi kèm giải thưởng 1 triệu USD do Google tài trợ, và Wigderson được đánh giá cao không chỉ vì thành tựu kỹ thuật mà còn là người cố vấn dẫn dắt các nhà nghiên cứu trẻ

Bối cảnh trao ACM Turing Award

  • ACM đã chọn Avi Wigderson là người nhận ACM A.M. Turing Award 2023
  • Lý do trao giải là những đóng góp nền tảng cho lý thuyết tính toán, thành tựu tái định hình cách hiểu về vai trò của tính ngẫu nhiên trong tính toán, và vai trò lãnh đạo trí tuệ trong khoa học máy tính lý thuyết suốt nhiều thập kỷ
  • Wigderson hiện là Herbert H. Maass Professor thuộc Khoa Toán tại Institute for Advanced Study ở Princeton, New Jersey

  • Các lĩnh vực hoạt động chính

    • lý thuyết độ phức tạp tính toán
    • thuật toán và tối ưu hóa
    • tính ngẫu nhiên và mật mã học
    • tính toán song song·phân tán
    • tổ hợp học và lý thuyết đồ thị
    • kết nối giữa khoa học máy tính lý thuyết với toán học·khoa học
    • ACM A.M. Turing Award thường được gọi là “Giải Nobel của ngành máy tính”, với 1 triệu USD tiền thưởng do Google, Inc. tài trợ
    • giải thưởng được đặt theo tên nhà toán học người Anh Alan M. Turing, người đã đặt nền móng toán học cho ngành tính toán

Những câu hỏi mà khoa học máy tính lý thuyết xử lý

  • Khoa học máy tính lý thuyết nghiên cứu nền tảng toán học của khoa học máy tính, đặt ra các câu hỏi như “bài toán này có thể giải bằng tính toán hay không” và “nếu giải được thì cần bao nhiêu thời gian và tài nguyên”
  • Lĩnh vực này cũng tìm hiểu các nguyên lý thiết kế thuật toán hiệu quả
  • Thuật toán là nền tảng tạo nên các công nghệ tính toán được sử dụng trong đời sống hằng ngày
  • Khoa học máy tính lý thuyết cũng theo đuổi những thách thức trí tuệ chưa chắc cải thiện ngay các ứng dụng thực tiễn, nhưng các đột phá nghiên cứu có thể dẫn tới tiến bộ ở nhiều lĩnh vực
    • mật mã học
    • sinh học tính toán
    • thiết kế mạng
    • học máy
    • điện toán lượng tử

Vì sao tính ngẫu nhiên quan trọng trong tính toán

  • Máy tính về bản chất là hệ thống tất định, trong đó với một đầu vào cho trước, tập lệnh của thuật toán sẽ quyết định duy nhất quá trình tính toán và đầu ra
  • Tính ngẫu nhiên chỉ trạng thái mà các sự kiện hay kết quả không có mẫu hình rõ ràng hoặc khả năng dự đoán
  • Trong thế giới thực có nhiều hiện tượng trông có vẻ ngẫu nhiên như hệ thống thời tiết, hiện tượng sinh học và hiện tượng lượng tử
  • Các nhà khoa học máy tính đã mở rộng thuật toán để chúng có thể thực hiện các lựa chọn ngẫu nhiên trong quá trình tính toán nhằm nâng cao hiệu quả
  • Nhiều bài toán chưa biết thuật toán tất định hiệu quả vẫn có thể được giải hiệu quả bằng thuật toán xác suất với xác suất lỗi nhỏ
    • xác suất lỗi này có thể được giảm một cách hiệu quả
  • Câu hỏi cốt lõi là liệu tính ngẫu nhiên có thực sự thiết yếu hay có thể loại bỏ, và chất lượng ngẫu nhiên cần thiết để các thuật toán xác suất thành công là gì
  • Hiểu rõ hơn cách tính ngẫu nhiên và giả ngẫu nhiên vận hành trong tính toán có thể dẫn đến việc phát triển thuật toán tốt hơn và hiểu sâu hơn về chính bản chất của tính toán

Những đóng góp nghiên cứu cốt lõi của Wigderson

  • Wigderson là người dẫn dắt nghiên cứu khoa học máy tính lý thuyết suốt 40 năm, có đóng góp nền tảng trong việc hiểu vai trò của tính ngẫu nhiên và giả ngẫu nhiên trong tính toán
  • Các nhà khoa học máy tính đã phát hiện mối liên hệ quan trọng giữa tính ngẫu nhiên và độ khó tính toán, tức việc xác định các bài toán tự nhiên không có thuật toán hiệu quả
  • Wigderson và các cộng sự đã công bố nhiều nghiên cứu có ảnh hưởng về hardness for randomness
  • Các nghiên cứu này cho thấy dưới các giả định tính toán tiêu chuẩn và được tin tưởng rộng rãi, mọi thuật toán thời gian đa thức ngẫu nhiên đều có thể được phi ngẫu nhiên hóa một cách hiệu quả
  • Kết quả này cho thấy tính ngẫu nhiên có thể không phải là điều bắt buộc cho tính toán hiệu quả
  • Dòng nghiên cứu đó đã thay đổi vai trò của tính ngẫu nhiên trong tính toán và cách người ta suy nghĩ về ngẫu nhiên

  • 3 bài báo tiêu biểu

    • Hardness vs. Randomness
      • đồng tác giả với Noam Nisan
      • giới thiệu một loại bộ sinh số giả ngẫu nhiên mới
      • chứng minh rằng có thể mô phỏng tất định hiệu quả các thuật toán ngẫu nhiên dưới những giả định yếu hơn rất nhiều so với trước đây
    • BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs
      • đồng tác giả với László Babai, Lance Fortnow, Noam Nisan
      • sử dụng hardness amplification
      • cho thấy dưới các giả định yếu hơn, bounded-error probabilistic polynomial time, tức BPP, có thể được mô phỏng trong thời gian dưới hàm mũ với vô hạn nhiều độ dài đầu vào
    • P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
      • đồng tác giả với Russell Impagliazzo
      • giới thiệu bộ sinh số giả ngẫu nhiên mạnh hơn
      • trình bày sự đánh đổi hardness-vs-randomness gần như tối ưu

Phạm vi ảnh hưởng và các thành tựu khác

  • Ba bài báo của Wigderson đã tạo ảnh hưởng vượt ra ngoài lĩnh vực tính ngẫu nhiên và phi ngẫu nhiên hóa, tới nhiều nhánh của khoa học máy tính lý thuyết
  • Các ý tưởng trong những bài báo này sau đó được sử dụng trong nhiều công trình có ảnh hưởng của các nhà nghiên cứu hàng đầu khác
  • Trong bài báo cùng Omer Reingold, Salil Vadhan và Michael Capalbo, ông đã đưa ra cấu trúc tổ hợp hiệu quả đầu tiên cho expander graph
    • expander graph là đồ thị thưa có tính chất liên thông mạnh
    • chúng có các ứng dụng quan trọng trong cả toán học và khoa học máy tính lý thuyết
  • Ngoài tính ngẫu nhiên, Wigderson còn thể hiện vai trò lãnh đạo trí tuệ ở các lĩnh vực sau
    • multi-prover interactive proofs
    • mật mã học
    • độ phức tạp mạch

Cố vấn và đánh giá

  • Wigderson được công nhận là một người cố vấn và đồng nghiệp được kính trọng, không chỉ nhờ những đóng góp kỹ thuật đột phá mà còn vì đã hướng dẫn nhiều nhà nghiên cứu trẻ
  • Kiến thức sâu rộng, năng lực kỹ thuật, sự gần gũi, nhiệt huyết và hào phóng của ông được xem là những yếu tố đã thúc đẩy nhiều nhà nghiên cứu trẻ xuất sắc theo đuổi sự nghiệp trong khoa học máy tính lý thuyết
  • Chủ tịch ACM Yannis Ioannidis cho biết Wigderson cũng đã nhận Abel Prize, vinh dự thường được xem là danh giá nhất cho thành tựu trọn đời trong toán học
  • Ioannidis đánh giá rằng toán học là nền tảng của khoa học máy tính, và công trình của Wigderson đã kết nối nhiều phân ngành toán học với khoa học máy tính lý thuyết
  • Phó chủ tịch cấp cao của Google Jeff Dean cho biết nghiên cứu của Wigderson về tính ngẫu nhiên và các chủ đề khác đã định hình chương trình nghị sự của khoa học máy tính lý thuyết trong 30 năm qua
  • Dean cũng nhấn mạnh rằng Wigderson là người tạo ra ý tưởng và định hướng nghiên cứu, đồng thời là người cố vấn truyền động lực để các nhà nghiên cứu trẻ theo đuổi các hướng đó

Turing Award và các bài báo quan trọng khác của Wigderson

  • A.M. Turing Award từ khi bắt đầu năm 1966 đã tôn vinh các nhà khoa học máy tính và kỹ sư tạo ra những hệ thống cũng như nền tảng lý thuyết dẫn dắt ngành công nghệ thông tin
  • Thành tích giải thưởng của Wigderson bao gồm
    • Abel Prize
    • IMU Abacus Medal, tên gọi trước đây là Nevanlinna Prize
    • Donald E. Knuth Prize
    • Edsger W. Dijkstra Prize in Distributed Computing
    • Gödel Prize
  • Wigderson là ACM Fellow, đồng thời là thành viên của U.S. National Academy of Sciences và American Academy of Arts and Sciences

  • Các bài báo quan trọng khác

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-04-12
Ý kiến trên Hacker News

  • Hai bài báo chính của Wigderson được nhắc đến trong thông báo đều là đồng tác giả với Noam Nisan, một trong các giáo sư tạo ra khóa học online nổi tiếng From Nand to Tetris

    • Giáo sư Nisan cũng là một nhân vật xuất sắc. Sau khi đạt thành tựu hàng đầu trong lý thuyết tính toán, ông còn để lại ảnh hưởng lớn trong một lĩnh vực khá khác là lý thuyết trò chơi thuật toán
      Việc một người có thể đạt được những thành tựu đa dạng như vậy thật hay, và hệ thống cho phép sự linh hoạt đó cũng rất ấn tượng
    • Ông ấy cũng có sách. Gần đây đã có ấn bản thứ 2

  • Cũng có một bài viết hay của Quanta: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Thấy vui vì họ bắt Wigderson tạo đủ kiểu dáng khi chụp. Trông quá gượng gạo. Kiểu như “Nào, hãy ngồi lên chiếc ghế này và nhìn xa xăm ra ngoài cửa sổ”

    • Đoạn nói “tính hiệu quả phi lý của tính ngẫu nhiên” khiến Wigderson suy nghĩ về chính bản chất của tính ngẫu nhiên khá thú vị
      Tôi hiểu các lớp độ phức tạp là nói về hiệu năng trong trường hợp xấu nhất, nên muốn biết đại khái làm sao chứng minh rằng dù có bộ sinh giả ngẫu nhiên tốt và thuật toán ngẫu nhiên hóa tốt, thì không có tổ hợp RNG + seed + problem instance nào mất thời gian lũy thừa
    • Xem phần đính chính thì bài gốc nói Wigderson từng học University of Haifa, nhưng thực tế ông tốt nghiệp Technion ở Haifa, Israel
      Không hiểu sao phóng viên lại nhầm được chuyện này
    • Tư thế “ngồi trên ghế nhìn ra ngoài cửa sổ” trông như kiểu Martin Scorsese hoặc Sopranos. Như cảnh một tay gangster già trong viện dưỡng lão

  • Scott Aaronson có viết một bài về việc một bài giảng của Avi Wigderson đã ảnh hưởng thế nào đến con đường sự nghiệp của mình: https://scottaaronson.blog/?p=2925

  • “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness” có thêm thông tin: [1] và bản lưu trữ [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Muốn biết nên bắt đầu từ đâu nếu muốn theo kịp phần nghiên cứu của Wigderson về sự đánh đổi giữa độ khó và tính ngẫu nhiên
    Hiếm khi tôi chưa từng nghe đến người đoạt giải Turing, nhưng người này hoàn toàn nằm ngoài tầm nhìn của tôi

    • Xem sách của ông ấy là được: https://www.math.ias.edu/avi/book
    • Tôi tò mò “các giả định tính toán chuẩn và được tin rộng rãi” là gì
      Có lẽ ý là việc xấp xỉ xác suất cho bài toán NP-đầy đủ cũng không phải thời gian đa thức, hoặc tôi đang lẫn lộn liệu phiên bản đã loại bỏ tính ngẫu nhiên vẫn là thuật toán xấp xỉ hay không

  • Tôi vừa cầm cuốn sách của Wigderson lên đọc và đến giờ khá thích: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Nếu phục vụ nghiên cứu cá nhân và mục đích giáo dục, có thể xem bản thảo cuối cùng của sách ở đây: https://www.math.ias.edu/avi/book
    • Tôi đã xem sách và thấy trình độ có vẻ hợp với nghiên cứu sinh hoặc sinh viên năm cuối hơn
      Không biết có thể gợi ý cuốn nào trình bày các chủ đề tính toán cơ bản hơn cho người có nền tảng đại học ngành khoa học máy tính/toán nhưng đã hơi mai một không

  • Trong bài liên quan có câu này: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “Nếu một mệnh đề có thể chứng minh được, thì nó cũng có chứng minh không tiết lộ tri thức” — nghe như nổ tung đầu
    Cả câu “nếu đưa các bit giả ngẫu nhiên thay cho bit ngẫu nhiên vào thuật toán xác suất, ta sẽ có một thuật toán quyết định hiệu quả cho cùng bài toán” cũng đáng kinh ngạc đến vô lý
    AI cũng là tính toán xác suất, nên nếu tôi đọc đúng thì chẳng phải điều này nghĩa là có thể giảm độ phức tạp của các mô hình hiện nay đi vài bậc độ lớn sao. Nếu đây là hiểu lầm của người mới thì mong ai đó kéo tôi ra

    • Tôi không biết chính xác ý là gì, nhưng ít nhất không phải vậy. AI vốn đã dùng giả ngẫu nhiên và có tính quyết định
      Có ngoại lệ như một số chip tăng tốc AI kỳ lạ dùng tính toán analog để tăng hiệu suất
    • Tiếc là không phải. Thứ nhất, kết quả đó áp dụng cho bài toán quyết định, không phải bài toán tìm kiếm
      Thứ hai, thuật toán quyết định được tạo ra kém hiệu quả hơn nhiều so với thuật toán ngẫu nhiên hóa. Nó chỉ thuộc cùng lớp độ phức tạp dưới các giả định yếu mà thôi

  • Tôi thích đoạn này trong bài: “Ứng dụng không phải là động lực, nhưng ta biết rằng ngay cả trong nghiên cứu cơ bản cũng có thể tìm thấy công dụng. Hãy nghĩ đến Alan Turing. Ông viết một bài toán học logic về Entscheidungsproblem trên một tạp chí ít người biết. Ứng dụng không phải là động lực”
    Giống giai thoại chiếc đĩa của Feynman. Bắt đầu từ một phản ứng nhẹ nhàng trước thứ ông thấy trong căng-tin đại học, cuối cùng dẫn đến giải Nobel
    Nói rộng hơn, giới học thuật hiện đại đang đi theo hướng kìm nén chính kiểu khám phá dựa trên tò mò này

  • Theo ACM, Avi Wigderson được chọn là người nhận ACM A.M. Turing Award 2023 vì những đóng góp nền tảng cho lý thuyết tính toán, bao gồm việc định hình lại hiểu biết về vai trò của tính ngẫu nhiên trong tính toán, cũng như vì vai trò lãnh đạo trí tuệ trong nhiều thập kỷ trong khoa học máy tính lý thuyết
    Wigderson là Herbert H. Maass Professor tại khoa Toán của Institute for Advanced Study ở Princeton, New Jersey, và là nhân vật then chốt trong lý thuyết độ phức tạp tính toán, thuật toán và tối ưu hóa, tính ngẫu nhiên và mật mã học, tính toán song song và phân tán, tổ hợp, lý thuyết đồ thị, cùng các mối liên hệ giữa khoa học máy tính lý thuyết với toán học và khoa học
    Năm 2021 ông cũng nhận giải Abel, tạo thành một tổ hợp khá độc đáo khi nhận cả danh dự cao nhất của toán học lý thuyết/trừu tượng lẫn khoa học máy tính

    • Phần giao nhau giữa khoa học máy tính lý thuyết và toán học lớn hơn nhiều so với đa số mọi người nghĩ
      Ví dụ đơn giản, nhìn danh sách môn khoa học máy tính lý thuyết của MIT https://catalog.mit.edu/subjects/6/ sẽ thấy có bao nhiêu môn được mở chéo với course 18, tức Toán
    • Nói chặt chẽ thì vinh dự cao nhất của toán học là Fields Medal
      Tất nhiên tôi cũng chẳng ở vị thế để phán xét

  • Muốn được gợi ý tài liệu học về chủ đề xác suất/tính ngẫu nhiên và tính toán, từ thân thiện với người mới bắt đầu đến nâng cao
    Google đưa ra cuốn “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” của Eli Upfal và Michael Mitzenmacher, nhưng tôi chưa tìm được sách/bài viết/video nào thật sự nhập môn hoặc dành cho người mới