[日時] 2023年5月19日(金) 12:20--13:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 七島 幹人 (東京工業大学)
[題目(title)] A Duality between One-Way Functions and Average-Case Symmetry of Information
[概要(Abstract)] Consider two textbooks, Book A and Book B. Is the information in Book A about Book B equal to the information in Book B about Book A? Symmetry of Information is one of the most fundamental theorems in algorithmic information theory and asserts that such symmetry generally holds when the information is measured by Kolmogorov complexity, i.e., the minimum description length of a “time-unbounded” Turing machine that produces each textbook.The above is discussed in the computability realm in the sense that we are not concerned about computational resources. However, when we restrict our attention to the complexity realm, the question of whether fundamental theorems such as Symmetry of Information hold in the time-bounded setting is non-trivial. Particularly, Longpre and Watanabe (Inf. Comput. 1995) proved that the time-bounded variant of Symmetry of Information does not hold under secure cryptography, specifically, the existence of one-way functions.In the talk, we will present the converse, i.e., an “asymmetry” of time-bounded algorithmic information is sufficient to construct minimum cryptography. We will characterize the existence of one-way functions using an average-case variant of Symmetry of Information. Our proof involves various notions, such as extrapolation, conditional coding, and language compression, which we have shown to be equivalent in the average-case setting. We will also discuss an open question on characterizing the feasibility of NP (both in worst and average cases) by algorithmic information and present some partial progress towards this goal.The presentation will be given in Japanese and will be based on joint work with Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, and Igor Carboni Oliveira.