Thông cáo báo chí
tỷ lệ kèo bóng đá trực tuyến Lab có hai bài báo được chấp nhận tại ICALP 2026, hội nghị hàng đầu trong lĩnh vực khoa học máy tính lý thuyết
CyberAgent Co, Ltd (Trụ sở chính: Shibuya-ku, Tokyo, Chủ tịch kiêm Giám đốc điều hành: Takahiro Yamauchi, TSE Prime Market: Mã chứng khoán 4751) đã thông báo rằng hai bài báo của các nhà nghiên cứu Naoto Osaka, So Kumabe, Tomoya Uesato và những người khác thuộc tỷ lệ kèo bóng đá trực tuyến Lab, một tổ chức nghiên cứu và phát triển công nghệ trí tuệ nhân tạo, sẽ được trình bày tại hội nghị quốc tế về lĩnh vực khoa học máy tính lý thuyết, ICALP 2026 (EATCS Quốc tế lần thứ 53) Hội thảo chuyên đề về Automata, Ngôn ngữ và Lập trình)”※1
``ICALP'' là hội nghị quốc tế hàng đầu của Châu Âu, được tài trợ bởi Hiệp hội Khoa học Máy tính Lý thuyết Châu Âu (EATCS), bao gồm tất cả các lĩnh vực khoa học máy tính lý thuyết, bao gồm thuật toán, lý thuyết độ phức tạp tính toán và logic Hai bài báo được chấp nhận dự kiến sẽ được trình bày tại ICALP 2026, được tổ chức tại London, Anh, vào tháng 7 năm 2026
■Nền
Để hiện thực hóa một xã hội thông tin tiên tiến, các thuật toán xuất sắc để giải quyết các vấn đề phức tạp một cách hiệu quả là điều cần thiết Do đó, tầm quan trọng của các lý thuyết cơ bản tạo ra các thuật toán mới và làm rõ hiệu suất cũng như những hạn chế của chúng ngày càng tăng"Phòng thí nghiệm tỷ lệ kèo bóng đá trực tuyến" coi khoa học máy tính lý thuyết là một trong những lĩnh vực quan trọng hỗ trợ các công nghệ ứng dụng như tỷ lệ kèo bóng đá trực tuyến và khai thác dữ liệu, đồng thời tham gia vào nghiên cứu cơ bản tiên tiến với sự cộng tác của các trường đại học và viện nghiên cứu ở Nhật Bản và nước ngoài
Lần này, kết quả được công nhận trong hai chủ đề quan trọng về mặt lý thuyết và xã hội: ``chuyển đổi tổ hợp'' xử lý các thay đổi về trạng thái trong không gian trạng thái và ``độ phức tạp tính toán của các biểu thức chính quy hiện đại'' liên quan trực tiếp đến bảo mật
■Bài viết tóm tắt
「」Tác giả: Hung P Hoang (Đại học Công nghệ Vienna), Naoto Osaka (CyberAgent tỷ lệ kèo bóng đá trực tuyến Lab), Rin Saito (Đại học Tohoku), Yuma Tamura (Đại học Tohoku)
「」Tác giả: So Kumabe, Tomoya Uesato (CyberAgent tỷ lệ kèo bóng đá trực tuyến Lab)
| Chuyển đổi tổ hợp là một khuôn khổ để chuyển đổi từng bước một giải pháp này sang một vấn đề khác trong khi vẫn duy trì tính khả thi Trong nghiên cứu này, chúng tôi đã phân tích tính gần đúng của một bài toán gọi là "chuyển đổi tập độc lập" nhằm vào các tập độc lập, đây là một bài toán cơ bản trên đồ thị Cụ thể, chúng tôi đã phát triển thuật toán gần đúng đầu tiên cho đồ thị tổng quát và phát triển thuật toán gần đúng với độ chính xác cao hơn khi có những hạn chế về cấu trúc đồ thị Mặt khác, chúng tôi đã chứng minh giới hạn lý thuyết của độ phức tạp tính toán, điều này gây khó khăn cho việc giải quyết vấn đề này trên một độ chính xác gần đúng nhất định Kết quả này cải thiện các vấn đề chưa được giải quyết trong lý thuyết thuật toán và tối ưu hóa rời rạc, đồng thời dự kiến sẽ được áp dụng cho thiết kế hệ thống yêu cầu chuyển đổi trạng thái hiệu quả và an toàn |
| Có một cuộc tấn công tên là ``ReDoS (tấn công DoS sử dụng biểu thức chính quy)'' làm dừng hệ thống bằng cách đưa ra một chuỗi cần có thời gian để xử lý từ bên ngoài đến các biểu thức chính quy được sử dụng trong dịch vụ web Gần đây, nó được coi là nguy hiểm ngay cả khi phải mất khoảng O(N2) bình phương thời gian cho độ dài chuỗi đầu vào N và cần có một công cụ biểu thức chính quy tốc độ cao theo quan điểm an toàn Mặc dù có những cách triển khai an toàn các biểu thức chính quy cổ điển chạy trong thời gian tuyến tính O(N), nhưng có một vấn đề thực tế đã biết là chúng không hỗ trợ phần mở rộng "backreferences (biến)" được sử dụng rộng rãi Trong nghiên cứu này, chúng tôi đã giải quyết vấn đề này bằng cách tạo ra một thuật toán nâng cao mới chạy trong O(N log² N), gần như theo thời gian tuyến tính, nhắm mục tiêu vào lớp quan trọng thực tế là ``một biến'' và ``chỉ được tham chiếu một lần'' Mặt khác, nó cũng bộc lộ giới hạn lý thuyết rằng nếu không có giới hạn về số lượng tham chiếu ngay cả khi chỉ có một biến thì không thể tránh được thời gian bình phương theo giả thuyết độ phức tạp tính toán tiêu chuẩn Kết quả này đã mở đường cho các thuật toán tốc độ cao xử lý phần mở rộng của biểu thức chính quy được sử dụng trong thế giới thực Trong tương lai, người ta hy vọng rằng những thách thức lý thuyết tiếp theo để làm sáng tỏ "thời gian tuyến tính thực sự" và những tiến bộ trong việc hiện thực hóa và triển khai các công cụ biểu thức chính quy tốc độ cao sẽ dẫn đến sự phát triển của các lĩnh vực nghiên cứu mới, nơi lý thuyết và ứng dụng cùng tăng cường lẫn nhau |
■Tương lai
Kết quả của những nghiên cứu này là kết quả nghiên cứu cơ bản có thể góp phần phát triển nghiên cứu lý thuyết và được kỳ vọng sẽ thúc đẩy ứng dụng xã hội của các vấn đề không chỉ trong công ty chúng tôi mà còn trong lĩnh vực khoa học máy tính lý thuyết Trong tương lai, "Phòng thí nghiệm tỷ lệ kèo bóng đá trực tuyến" sẽ tiếp tục thúc đẩy nghiên cứu ứng dụng gần gũi với doanh nghiệp, cũng như cố gắng tiến hành nghiên cứu và phát triển với mục tiêu đóng góp học thuật cho nghiên cứu cơ bản
※1