Mikito Nanashima
Last Update: 2024.4.7
About Me
Name: Mikito Nanashima / 七島 幹人
I'm an assistant professor of the School of Computing at Tokyo Institute of Technology 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.
e-mail: 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
- theoretical computer science
- computational learning, computational complexity, cryptography, and proof complexity
- connections among the above and proof tools to bridge them: for example, reductions
- a complexity theoretic view of information
Publications
Link: [dblp]
[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, On Basing 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
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.9 - 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 @ Kuyshu 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