Updated on 2026/06/02

写真a

 
NANASHIMA MIKITO
 
Organization
School of Computing Associate Professor
Title
Associate Professor
Homepage
https://nanashima.github.io/
External link

Research Areas

  • Informatics / Theory of informatics

Papers

▼display all

Research Projects

  • メタ計算量に基づく平均時NP完全性理論の開拓

    Grant number：24K21317  2024.6 - 2030.3

    日本学術振興会  科学研究費助成事業  挑戦的研究(開拓)

    平原 秀一, 清水 伸高, 七島 幹人

    　 More details

    Grant amount：\26000000 （ Direct Cost: \20000000 、 Indirect Cost：\6000000 ）

    researchmap

  • 学習とデータ圧縮に関する計算複雑さ

    Grant number：24030423  2024 - 2026

    科学技術振興機構  戦略的な研究開発の推進/戦略的創造研究推進事業/ACT-X

    七島 幹人

    　 More details

    学習アルゴリズムが予測のために⽤いる仮説の記述の簡潔さと、その仮説を発⾒するために必要となる計算量、及び、学習アルゴリズムの能⼒に対する理論保証とデータの圧縮可能性の関係の解析を中⼼とした研究を⾏います。得られた結果を元に、NP 困難性に基づく暗号の安全性証明という重要未解決問題の本質的進展と、理論計算機科学のアイデアを取り込んだ⾰新的学習アルゴリズム構成・活⽤法の創出を⽬指します。

    researchmap

  • A Study on Breaking and Avoiding Relativization Barriers against Constructing One-Way Functions

    Grant number：23K19957  2023.8 - 2025.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Research Activity Start-up

    　 More details

    Grant amount：\2860000 （ Direct Cost: \2200000 、 Indirect Cost：\660000 ）

    researchmap

  • Theoretical Foundations of Resource-Bounded Quantum Computation

    Grant number：22H00522  2022.4 - 2027.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (A)

    　 More details

    Grant amount：\40560000 （ Direct Cost: \31200000 、 Indirect Cost：\9360000 ）

    researchmap

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

    Grant number：21J11263  2021.4 - 2023.3

    日本学術振興会  科学研究費助成事業 特別研究員奨励費  特別研究員奨励費

    七島 幹人

    　 More details

    Grant amount：\1100000 （ Direct Cost: \1100000 ）

    本年度は，暗号理論と計算複雑さ理論の中心的概念であるNPの最悪時困難性の間にある諸概念と学習の計算論的困難性（以下，学習困難性と呼ぶ）の関係性を調査し，暗号・計算・学習の理論をまたぐ，以下の重要な関係性を得た．
    (1) 平均時学習困難性と追加入力付き暗号一方向性関数の等価性 :追加入力付き暗号一方向性関数とは，標準的な暗号の安全性要件を自然に弱めた暗号プリミティブである．既存研究では，そのような追加入力付き暗号一方向性関数の存在が，学習困難性を示すのに十分であることが知られていた．本研究では従来の学習モデルの要件を平均時に緩和したモデルを導入し，既存研究の逆方向，すなわち，平均時学習困難性が追加入力付き暗号一方向性関数の存在に必要十分であることを証明した．
    (2) NPの平均時容易性を基にした，効率的学習可能性の証明：従来，計算論的学習理論で議論される学習要件は任意の関数を任意の分布上で学習するという最悪時の要件を持ち，この点が従来の暗号理論とのギャップの大きな要因となっていた．本研究ではそのような分布の条件を任意の分布から任意の回路モデルで効率的にサンプル可能な分布に緩和することで，そのようなモデルにおける十分自然でかつ強い学習可能性が，NPの平均時容易性のみから従うことを証明した．加えて，平均時容易性を基にした学習可能性の証明において，このような分布条件の緩和が，相対化する手法と呼ばれる現在の標準的証明手法の枠組みの中で本質的に不可欠であるという理論的根拠を与えた．

    researchmap

  • Research on Difficulty of Proving Efficient Learnability

    2019.10 - 2022.3

    Japan Science and Technology Agency  [Math and Info] Frontier of mathematics and information science 

    Mikito Nanashima

    　 More details

    Authorship：Principal investigator  Grant type：Competitive

    researchmap

▼display all