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

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

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

基于第一年的结果，重点是学习困难，重点关注单向功能的构建，这是基于NP的最坏情况的加密理论的核心概念，我们使用以下自下而上/自上而下的方法进行了研究。随着将最坏难以假设转换为加密安全性的动机，自下而上的方法对转换方法的可扩展性进行了研究，从最坏的难度到NP无错误的平均平均难度，这是第一年，并明确定义了有关无时间误差难度的新证据的障碍，我们可以确定解决方案的平均障碍，我们可以确定解决方案的问题。为了放松为最坏的难度假设构建加密代码所必需的假设，我们研究了遵循没有单向函数的算法属性。在第一年，据透露，没有单向功能遵循强大的平均学习可能性。今年，我们应用了那里的方法，并专注于信息对称性，这是一个抽象的概念，可以期望与理论计算机科学中的概念建立更广泛的关系，并且我们获得了基于信息函数的存在的新的基于信息的理论表征。此外，通过将第一年的结果应用于低复杂性类别，尤其是平行恒定的时间计算类别，我们基于平行恒定的恒定时间估计多项式弹力弹力弹力范围数字的学习难度获得了新的施工方法和表征的结果，这在密码学理论中是重要的基础。

项目成果

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

MIT(米国)

麻省理工学院（美国）

A Theory of Heuristic Learnability

启发式学习能力理论

• 发表时间: 2021
• 作者: 松本徳文;中川大也;上田正仁;Mikito Nanashima
• 通讯作者: Mikito Nanashima