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

• Khoa học máy tính lý thuyết xử lý nền tảng toán học của lĩnh vực điện toán. Nó đặt ra các câu hỏi như: "Vấn đề này có thể được giải bằng tính toán không?", "Nếu vấn đề này có thể được giải bằng tính toán thì cần bao nhiêu thời gian và tài nguyên?". Đồng thời, nó cũng khám phá cách thiết kế các thuật toán hiệu quả. Mọi công nghệ điện toán ảnh hưởng đến cuộc sống của chúng ta đều trở nên khả thi nhờ thuật toán. Việc hiểu các nguyên lý của những thuật toán mạnh và hiệu quả không chỉ giúp đào sâu hiểu biết về khoa học máy tính mà còn cả về các quy luật của tự nhiên. Khoa học máy tính lý thuyết được biết đến là một lĩnh vực đặt ra những thách thức trí tuệ hấp dẫn, và tuy thường không liên quan trực tiếp đến việc cải thiện các ứng dụng thực tiễn của điện toán, các đổi mới nghiên cứu trong lĩnh vực này lại dẫn tới tiến bộ trong gần như mọi lĩnh vực như mật mã học, sinh học tính toán, thiết kế mạng, máy học và điện toán lượng tử.

• Về cơ bản, máy tính là một hệ thống tất định. Khi áp dụng một tập lệnh của thuật toán cho một đầu vào nhất định, quá trình tính toán được xác định duy nhất, và đặc biệt là đầu ra cũng được xác định. Nói cách khác, thuật toán tất định tuân theo những mẫu hình có thể dự đoán được. Ngược lại, tính ngẫu nhiên là sự thiếu vắng một mẫu hình được xác định rõ hoặc khả năng dự đoán của các sự kiện/kết quả. Vì thế giới chúng ta đang sống dường như đầy rẫy các sự kiện ngẫu nhiên (như hệ thống thời tiết, các hiện tượng sinh học/lượng tử, v.v.), các nhà khoa học máy tính đã tăng cường cho thuật toán khả năng đưa ra lựa chọn ngẫu nhiên trong quá trình tính toán để nâng cao hiệu quả. Trên thực tế, nhiều bài toán mà chưa biết đến thuật toán tất định hiệu quả đã được giải hiệu quả bằng các thuật toán xác suất (dù có một xác suất lỗi nhỏ nhưng có thể giảm xuống hiệu quả). Tuy nhiên, tính ngẫu nhiên có thực sự thiết yếu hay có thể loại bỏ được? Chất lượng ngẫu nhiên cần thiết cho sự thành công của các thuật toán xác suất là gì?

• Trong suốt 40 năm, Tiến sĩ Avi Wigderson đã dẫn dắt nghiên cứu khoa học máy tính lý thuyết và có những đóng góp nền tảng cho việc hiểu vai trò của tính ngẫu nhiên và giả ngẫu nhiên trong điện toán. Các nhà khoa học máy tính đã phát hiện ra một mối liên hệ đáng chú ý giữa tính ngẫu nhiên và độ khó tính toán (việc xác định các bài toán tự nhiên không có thuật toán hiệu quả). Tiến sĩ Wigderson cùng các cộng sự đã thực hiện một chuỗi nghiên cứu có ảnh hưởng rất lớn về việc đánh đổi độ khó để lấy tính ngẫu nhiên. Họ đã chứng minh rằng, 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 xác suất thời gian đa thức đều có thể loại bỏ tính ngẫu nhiên một cách hiệu quả (tức là có thể trở thành hoàn toàn tất định). Nói cách khác, tính ngẫu nhiên không phải là yếu tố thiết yếu cho tính toán hiệu quả. Chuỗi nghiên cứu này đã cách mạng hóa hiểu biết của chúng ta về vai trò của tính ngẫu nhiên trong điện toán và cách chúng ta suy nghĩ về tính ngẫu nhiên.

Các đóng góp của Tiến sĩ Wigderson

• "Hardness vs. Randomness" (đồng tác giả với Noam Nisan): Bài báo này, cùng với nhiều đóng góp khác, đã giới thiệu một kiểu bộ sinh giả ngẫu nhiên mới và 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 hóa 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): Bài báo này sử dụng "hardness amplification" để chứng minh rằng bounded-error probabilistic polynomial time (BPP) có thể được mô phỏng trong thời gian dưới hàm mũ đối với vô hạn nhiều độ dài đầu vào dưới các giả định yếu hơn.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (đồng tác giả với Russell Impagliazzo): Bài báo này đã giới thiệu một bộ sinh giả ngẫu nhiên mạnh hơn với sự đánh đổi hardness vs randomness về bản chất là tối ưu.

• Vượt ra ngoài nghiên cứu liên quan đến tính ngẫu nhiên, Tiến sĩ Wigderson còn thể hiện vai trò lãnh đạo học thuật trong nhiều lĩnh vực khác của khoa học máy tính lý thuyết như chứng minh tương tác đa người chứng, mật mã học và độ phức tạp mạch.

Ý kiến của GN⁺

• Nghiên cứu của Wigderson chứng minh mối quan hệ giữa tính ngẫu nhiên và độ phức tạp tính toán trên phương diện toán học có ý nghĩa lớn ở khía cạnh giao thoa giữa khoa học máy tính và toán học. Đặc biệt, việc chứng minh rằng nhiều thuật toán vốn phụ thuộc vào tính ngẫu nhiên thực ra có thể được hiện thực hóa một cách tương đương bằng phương pháp tất định được đánh giá là đã mở ra một chân trời mới cho khoa học máy tính.

• Ngoài ra, việc tiếp cận mối quan hệ giữa hiệu quả và độ khó bằng toán học cũng có vẻ sẽ trở thành một chủ đề nghiên cứu quan trọng của khoa học máy tính lý thuyết. Việc những bài toán càng khó lại càng có khả năng tồn tại các thuật toán hiệu quả tương ứng là một insight không hề trực quan.

• Mặt khác, việc Giáo sư Wigderson nhấn mạnh sự kết hợp giữa toán học và khoa học máy tính để thúc đẩy sự phát triển của khoa học máy tính lý thuyết, đồng thời nỗ lực đào tạo thế hệ kế cận, dường như sẽ là một tấm gương tốt cho các thế hệ học giả tiếp theo. Đặc biệt, việc ông từng nhận cả Giải Abel của toán học lẫn Giải Turing của khoa học máy tính có thể xem là một ví dụ mang tính biểu tượng cho tầm quan trọng của khoa học máy tính lý thuyết.

[GN⁺]

Ý kiến trên Hacker News

• Avi Wigderson đã nhận giải ACM A.M. Turing Award 2023. Ông được ghi nhận vì những đóng góp nền tảng cho lý thuyết tính toán, đặc biệt là 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 vai trò lãnh đạo học thuật trong khoa học máy tính lý thuyết suốt nhiều thập kỷ.

• Wigderson là một nhân vật hàng đầu trong các lĩnh vực 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 và phân tán, tổ hợp học, lý thuyết đồ thị, đồng thời còn đóng vai trò cầu nối giữa khoa học máy tính lý thuyết với toán học và khoa học.

• Một trong những thành tựu chính của Wigderson là khám phá ra mối liên hệ đáng kinh ngạc giữa tính ngẫu nhiên và độ khó tính toán. Nghiên cứu của ông cho thấy tính ngẫu nhiên không nhất thiết là điều kiện bắt buộc cho tính toán hiệu quả.

• Năm 2021, ông cũng nhận giải Abel Prize, qua đó sở hữu thành tích hiếm có khi giành được cả hai vinh dự cao nhất trong toán học lý thuyết/trừu tượng và khoa học máy tính.

• Cuốn sách "Mathematics and Computation" của Wigderson mới được xuất bản gần đây và đang nhận được nhiều đánh giá tích cực.

• Theo các kết quả nghiên cứu của ông, nếu một mệnh đề có thể được chứng minh thì cũng có thể có zero-knowledge proof, và nếu áp dụng số giả ngẫu nhiên cho các thuật toán xác suất thì có thể thu được thuật toán tất định hiệu quả cho cùng bài toán. Điều này cho thấy có thể giảm mạnh độ phức tạp của các mô hình tính toán xác suất như AI.