About
Name: Mikito Nanashima / 七島幹人
I am an assistant professor in the School of Computing at Institute of Science Tokyo, Japan.
I received my Ph.D. under the supervision of Prof. Toshiya Itoh. During my undergraduate studies, I was also advised by Prof. Osamu Watanabe.
I was a visiting student at the Simons Institute for the Meta-Complexity program
in February and March 2023.
To be honest, I am not very confident in my English skills. If you happen to see me at an international conference, please go easy on me 🙇
Contact
Email: nanashima at comp dot isct dot ac dot jp (replace dot and at properly)
Research
- Theoretical Computer Science
- Computational Complexity
- Dichotomy between Learning and Cryptography
- Complexity-Theoretic Inductive Inference
Publications
Link: [dblp]
[14] S. Hirahara and M. Nanashima, Complexity-Theoretic Universal Inductive Inference, in STOC2026 (to appear).
[13] S. Hirahara and M. Nanashima, A Sharp Characterization of Pessiland, in STOC2026 (to appear).
[12] S. Hirahara, Z. Lu, and M. Nanashima, Optimal Coding for Randomized Kolmogorov Complexity and Its Applications, in FOCS2024 [full].
[11] S. Hirahara and M. Nanashima, One-Way Functions and Zero Knowledge, in STOC2024 [full].
[10] S. Hirahara and M. Nanashima, Learning in Pessiland via Inductive Inference, in FOCS2023 [full].
[9] S. Hirahara, R. Ilango, Z. Lu, M. Nanashima, and I. C. Oliveira, A Duality Between One-Way Functions and Average-Case Symmetry of Information, in STOC2023 [full].
[8] S. Hirahara and M. Nanashima, Learning versus Pseudorandom Generators in Constant Parallel Time, in ITCS2023 [full].
[7] S. Hirahara and M. Nanashima, Finding Errorless Pessiland in Error-Prone Heuristica, in CCC2022 [proc].
[6] S. Hirahara and M. Nanashima, On Worst-Case Learning in Relativized Heuristica, in FOCS2021 [full].
[5] M. Nanashima, A Theory of Heuristic Learnability, in COLT2021 [proc].
[4] M. Nanashima, Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions, in ITCS2021 [proc] [full].
[3] M. Nanashima, Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning, in COLT2020 [proc].
[2] M. Nanashima, A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields, in ALT2020 [proc]. (M.Sc. thesis)
[1] M. Nanashima, Cryptographic Limitations on Polynomial-Time a Posteriori Query Learning, in IWOCA2018 [proc]. (B.Sc. thesis)
Fellowships & Projects
Principal Investigator
2024.10 - 2027.3 JST ACT-X NextAI Math Info, Computational Complexity of Learning and Compression.
2023.9 - 2025.3 JSPS Grant-in-Aid for Research Activity Start-up, A Study on Breaking and Avoiding Relativization Barriers against Constructing One-Way Functions.
2019.10 - 2022.3 JST ACT-X Math. and Info., Research on Difficulty of Proving Efficient Learnability.
2020.4 - 2021.3 Tokyo Tech Tsubame Scholarship for Doctoral Students.
2021.4 - 2023.3 JSPS Research Fellowship for Young Scientists (DC2).
Co-Investigator
2024.4 - Now JSPS Grant-in-Aid for Challenging Research (Pioneering), Average-Case NP-Completeness Theory via Meta-Complexity.
2023.4 - Now JSPS Grant-in-Aid for Scientific Research (A), Theoretical Foundations of Resource-Bounded Quantum Computation.
Prize
The 13th JSPS Ikushi Prize [link].
Teaching
Instructor
2023-, Programming I (co-instructed with Ken Wakita)
TA
2018, 19, 22, Introduction to Algorithms and Data Structures
2018, 19, Information Literacy I
2018, Programming I
2018, Information Literacy II
Activities
Talks (except for invited talks on the aforementioned papers)
Learning versus Cryptography (in Japanese), in Final Lecture and Workshop of Prof. Osamu Watanabe @ Science Tokyo, 2025, March.
Universal Extrapolation, in the EnCORE Workshop on Meta-Complexity as the Bridge Between Learning and Cryptography @ UC Sandiego (EnCORE Institute), 2025, February.
Math on Difficulties of Computation (in Japanese) @ Tokyo Tech Open Campus, 2023, August [recorded video]. (aimed at high school students in Japan)
Kolmogorov Complexity and its Algorithmic and Cryptographic Benefits (in Japanese), in Workshop on Mathematics of Next-Generation Cryptography for Secure Utilization of Quantum Information @ Kyushu Univ. (hybrid), 2022, August.
Hardness of Learning, Auxiliary-Input Cryptography, and Meta-Complexity (in Japanese), in the seminar for International Research Unit of Quantum Information @ Kyoto Univ. (zoom), 2021, July.
A Story of Computation, Cryptography, and the Gaps (in Japanese), in the course of "Literacy of Computing" @ Tokyo Tech., 2020, 2021.
External Reviews
Conferences: RANDOM2021, STACS2022, CSR2022, CCC2022, ISAAC2022, STOC2023, CCC2023, FOCS2023, and more...
Journal: SICOMP, TCS, TheoretiCS, Computational Complexity, and more...