学習階層の解析と計算論的学習理論の新展開

学习层次分析及计算学习理论新进展

• 批准号: 21J11263
• 负责人: 七島 幹人
• 金额: $ 0.7万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-28 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21J11263/
• 关键词: 計算論的学習理論; 学習可能性; 計算複雑性理論; 暗号理論; 平均時計算複雑性; PAC学習; 一方向性関数

NPの最悪時困難性を基とした暗号理論の中核的概念である一方向性関数の構成に向け，第一年次に得られた学習困難性に着目した成果を踏まえた上で，以下のボトムアップ/トップダウン的アプローチによる研究を進めた．ボトムアップ的アプローチでは，最悪時困難性仮定を暗号の安全性に変換していくという動機のもと，第一年次の成果である，学習の最悪時困難性からNPの誤りなし平均時困難性への変換手法の拡張可能性について研究を行い，平均時誤りあり・誤りなし困難性，及び，学習困難性に関する新たな証明の障壁の明示化によって，真に課題解決に有効となり得る手法の特定を行った．トップダウン的アプローチでは，暗号の構成に必要な仮定を最悪時困難性仮定まで緩和していくという動機のもと，一方向性関数の非存在から従うアルゴリズム的性質の研究を進めた．第一年次では，一方向性関数の非存在から強い平均時学習可能性が従うことが明らかになっていた．本年度はそこでの手法を応用し，理論計算機科学の諸概念とのより広い関係が期待出来る抽象的概念である，情報の対称性に着目することで，一方向性関数の存在の新たな情報基礎論的特徴付けを得た．加えて，第一年次の成果を低複雑性クラス，特に，並列定数時間計算可能クラスに応用することで，暗号理論における重要プリミティブである並列定数時間計算可能多項式ストレッチ疑似乱数生成器の学習困難性を基にした新しい構成アプローチと特徴付けの結果を得た．

The concept of NP's most difficult language is the construction of a directional language. The first year of NP's most difficult language is the achievement of NP's most difficult language. In the first year of the study, the results showed that the learning difficulty was the highest, and the learning difficulty was the lowest. The problem is solved by specific methods. A study on the nature of a directional relationship between the existence of a non-existence and the existence of a non-existence is being carried out. In the first year, a directional relation number does not exist. This year, the concept of theoretical computer science and the relationship between them are expected to come out, and the characteristics of a new information-based theory of directional relations are obtained. The results of the first year are low complexity, especially the results of parallel fixed number time calculation.

项目成果

A Duality Between One-Way Functions and Average-Case Symmetry of Information

单向函数与信息平均情况对称性之间的一种对偶性

• 发表时间: 2023
• 期刊: The 55th ACM Symposium on Theory of Computing (STOC 2023) (to appear)
• 作者: S. Hirahara;R. Ilango;Z. Lu;M. Nanashima
• 通讯作者: M. Nanashima

Finding Errorless Pessiland in Error-Prone Heuristica

在易错启发式中寻找无错 Pesiland

• 发表时间: 2022
• 期刊: 37th Computational Complexity Conference (CCC 2022), Leibniz International Proceedings in Informatics
• 作者: Hiroto Mitani;Riouhei Nakatani;Naoki Yoshida;S. Hirahara and M. Nanashima
• 通讯作者: S. Hirahara and M. Nanashima

Learning Versus Pseudorandom Generators in Constant Parallel Time

恒定并行时间内的学习与伪随机生成器

• 发表时间: 2023
• 期刊: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz International Proceedings in Informatics
• 作者: Ikeda Tatsuhiko;Chinzei Koki;Sato Masahiro;OTA Tomohiro （太田知宏）;明星つきこ;S. Hirahara and M. Nanashima
• 通讯作者: S. Hirahara and M. Nanashima

University of Warwick/University of Oxford(英国)

华威大学/牛津大学（英国）

MIT(米国)

麻省理工学院（美国）