Hai nhà toán học Việt Nam và nhóm Google độc lập giải bài toán mở hơn một thập kỷ của khoa học máy tính
Vahab Mirrokni - Phó Chủ tịch Google Research và người lãnh đạo các nhóm nghiên cứu về Thuật toán và Tối ưu hóa tại Google - vừa công bố chứng minh của nhóm Google cho giả thuyết Courtade–Kumar, đồng thời ghi nhận và chúc mừng lời giải độc lập của nhóm Ky–Tran.
https://x.com/mirrokni/status/2102239175697207395
Courtade–Kumar là một giả thuyết nổi tiếng ở giao điểm giữa Lý thuyết thông tin, Giải tích hàm Boolean và Khoa học máy tính lý thuyết. Phát biểu của nó khá đơn giản: khi một chuỗi bit đi qua một kênh nhiễu, trong số tất cả các hàm Boolean, cách giữ lại nhiều thông tin nhất về đầu vào chỉ là đọc một tọa độ duy nhất. Tuy nhiên, phát biểu tưởng như đơn giản này đã tồn tại hơn một thập kỷ và thu hút rất nhiều hướng tiếp cận từ Fourier analysis, entropy, hypercontractivity cho tới các bất đẳng thức đẳng chu.
Trong bài viết công bố kết quả, Mirrokni gọi Courtade–Kumar là một “bài toán mở trung tâm tồn tại lâu năm ở giao điểm giữa lý thuyết thông tin và giải tích hàm Boolean”. Ông cũng nhắc lại rằng trong chuyên khảo của Yu và Tan, giả thuyết này được mô tả là “một trong những bài toán mở quan trọng nhất của lý thuyết thông tin”.
Theo Mirrokni, ý nghĩa của CK không chỉ nằm ở bài toán cực đại hóa thông tin tương hỗ. Giả thuyết còn gắn với một họ rộng các bài toán cực trị, các bất đẳng thức hàm và bất đẳng thức đẳng chu trên không gian Boolean, trong đó có những liên hệ với các bất đẳng thức của Talagrand, Bobkov và, ở một số chế độ, với bất đẳng thức đẳng chu theo cạnh cổ điển của Harper.
Điều đặc biệt là gần như cùng thời điểm, hai nhóm nghiên cứu hoàn toàn độc lập đã đi đến lời giải bằng hai con đường rất khác nhau. Nhóm Google và các cộng tác viên tại CUHK phát triển một hướng dựa nhiều vào phương trình vi phân, tính toán và formal verification, với một phần chứng minh được kiểm chứng bằng Lean. Trong khi đó, bài báo “Dictators are most informative” của Vu Khac Ky (FPTU) và Tuan Tran (USTC) đi theo một hướng khác, dựa trên entropy và spectral analysis.
Mirrokni công khai nhấn mạnh rằng hai chứng minh sử dụng những cách tiếp cận rất khác nhau về bản chất, đồng thời gửi lời chúc mừng tới Ky và Tran về thành tựu này.
Điều đáng chú ý là hai nhóm đi đến cùng một kết quả gần như đồng thời nhưng bằng những phương pháp rất khác nhau. Với một bài toán đã tồn tại hơn mười năm, việc có hai chứng minh độc lập như vậy cũng cho thấy cấu trúc của bài toán phong phú hơn nhiều so với một lời giải đơn lẻ.