Mikito Nanashima

Last Update: 2024.10.8

About Me

Name: Mikito Nanashima / 七島 幹人

I'm an assistant professor of the School of Computing at Institute of Science Tokyo in Japan.

I received Ph.D. under the supervision of Prof. Toshiya Itoh. I had also been advised by Prof. Osamu Watanabe during my undergraduate.
I was visiting Simons institute Meta-Complexity program as a visiting student on Feb. and Mar. 2023.

Email: nanashima at c dot titech dot ac dot jp (replace dot and at properly)

To be honest, I'm not confident in my English skills. If you see me at some international conference, please go easy on me🙇

Research Interests

Publications

Link: [dblp]

[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[paper].

[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[paper].

[4] M. Nanashima, Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions, in ITCS2021 [paper] [full].

[3] M. Nanashima, Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning, in COLT2020[paper].

[2] M. Nanashima, A Non-Trivial Algorithm Enumerating Relevant Features over Finite Fields, in ALT2020[paper]. (M.Sc. thesis)

[1] M. Nanashima, Cryptographic Limitations on Polynomial-Time a Posteriori Query Learning, in IWOCA2018[paper]. (B.Sc. thesis)

Fellowships and 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

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 Experience

Instructor

2023-, Programming I (Exercise Part), 3Q.

TA

2018, 19, 22, Introduction to Algorithms and Data Structures, 2Q.

2018, 19, Information Literacy I, 1Q.

2018, Programming I, 3Q.

2018, Information Literacy II, 2Q.

Other Activities

Talks (except for invited talks on the aforementioned papers)

Math on Difficulties of Computation (in Japanese) @ Tokyo Tech Open Campus, 2023, August[recorded video]. (this is aimed at high school students in Japan)

Kolmogorov Complexity and its Algorithmic and Cryptographic Benefits (invited, 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: Computational Complexity, SICOMP