HIRAHARA Shuichi

Field of Studies	Mathematical and Information Science
Program	Informatics
Parent Institute	National Institute of Informatics
Position	Associate Professor
Link	https://researchmap.jp/shuichi.hirahara/ https://nrid.nii.ac.jp/ja/nrid/1000080848440/

researchmap

average-case complexity,meta-complexity,Kolmogorov Complexity,Minimum Circuit Size Problem,Complexity Theory

- One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
- DOI: 10.1007/s00224-022-10113-9
- Publish year: 2024
- Journal: Theory of Computing Systems
- URL: https://researchmap.jp/shuichi.hirahara/published_papers/48962230
- One-Way Functions and Zero Knowledge.
- DOI: 10.1145/3618260.3649701
- Publish year: 2024
- Journal: STOC
- URL: https://researchmap.jp/shuichi.hirahara/published_papers/47178194
- Symmetric Exponential Time Requires Near-Maximum Circuit Size.
- DOI: 10.1145/3618260.3649624
- Publish year: 2024
- Journal: STOC
- URL: https://researchmap.jp/shuichi.hirahara/published_papers/47178195
- Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
- DOI: 10.1109/FOCS61266.2024.00030
- Publish year: 2024
- Journal: FOCS
- URL: https://researchmap.jp/shuichi.hirahara/published_papers/48962231
- One-Way Functions and pKt Complexity.
- DOI: 10.1007/978-3-031-78011-0_9
- Publish year: 2024
- Journal: TCC (1)
- URL: https://researchmap.jp/shuichi.hirahara/published_papers/48962232

- メタ計算量に基づく平均時NP完全性理論の開拓
- 2024-2029
- keywords: 平均時計算量, メタ計算量, 埋め込みクリーク予想
- URL: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24K21317/

- Kolmogorov Complexity Characterizes Statistical Zero Knowledge
- Author: 平原秀一
- Publish date: 2023
- Journal: Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
- URL: https://cir.nii.ac.jp/crid/1010861618231226370
- Learning Versus Pseudorandom Generators in Constant Parallel Time
- Author: 平原秀一
- Publish date: 2023
- Journal: Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
- URL: https://cir.nii.ac.jp/crid/1010861618231226388
- Average-Case hardness of NP and PH from worst-case fine-grained assumptions
- Author: 平原秀一
- Publish date: 2022
- Journal: Proc. of Innovations in Theoretical Computer Science Conference
- URL: https://cir.nii.ac.jp/crid/1010298668234502279
- Excluding PH Pessiland
- Author: 平原秀一
- Publish date: 2022
- Journal: Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
- URL: https://cir.nii.ac.jp/crid/1010861618231226383
- Finding Errorless Pessiland in Error-Prone Heuristica
- Author: 平原秀一
- Publish date: 2022
- Journal: Proceedings of the 37th Computational Complexity Conference (CCC 2022)
- URL: https://cir.nii.ac.jp/crid/1010861618231226256