Hirahara Shuichi 平原秀一

Researcher Number	80848440
Affiliation (Current)	2025: 国立情報学研究所, 情報学プリンシプル研究系, 准教授
Affiliation (based on the past Project Information) *help	2020 – 2024: 国立情報学研究所, 情報学プリンシプル研究系, 准教授 2019 – 2020: 国立情報学研究所, 情報学プリンシプル研究系, 助教
Review Section/Research Field	Principal Investigator Medium-sized Section 60:Information science, computer engineering, and related fields Except Principal Investigator Basic Section 60010:Theory of informatics-related / Transformative Research Areas, Section (IV) / Medium-sized Section 60:Information science, computer engineering, and related fields
Keywords	Principal Investigator 埋め込みクリーク予想 / メタ計算量 / 平均時計算量 Except Principal Investigator 量子計算量理論 / 量子分散計算 / 量子アルゴリズム / 離散最適化 / 組合せ最適 / 計算理論 / アルゴリズム … More / グラフ理論 / グラフ / 計算量 / 組合せ最適化 / グラフアルゴリズム / 量子計算の基礎 / SAT問題 / 質問計算量 / 回路計算量 / 最小回路サイズ問題 / 情報セキュリティ技術 / 情報セキュリティ / 学習可能性 / 平均時計算量 / Ｐ≠ＮＰ予想 / 機械学習 / PAC学習困難性 / 計算論的暗号 / 平均時計算困難性 / 多項式時間階層 / 最小記述量計算 / 一方向関数 / 学習計算困難さ / 平均時計算複雑度 / 最小記述量 / 計算論的暗号理論 / 計算論的学習理論 / 平均時時間計算量 / 最悪時時間計算量 / メタ計算 / P≠NP予想 / 最小記述量計算問題 / 計算複雑度理論 Less

メタ計算量に基づく平均時NP完全性理論の開拓Principal Investigator
- Principal Investigator
  
  平原秀一
- Project Period (FY)
  2024 – 2029
- Research Category
  
  Grant-in-Aid for Challenging Research (Pioneering)
- Review Section
  
  Medium-sized Section 60:Information science, computer engineering, and related fields
- Research Institution
  National Institute of Informatics
New computational models for algorithms and discrete optimization
- Principal Investigator
  
  河原林健一
- Project Period (FY)
  2020 – 2024
- Research Category
  
  Grant-in-Aid for Transformative Research Areas (A)
- Review Section
  
  Transformative Research Areas, Section (IV)
- Research Institution
  National Institute of Informatics
Quantum Algorithms for Large-Scale Quantum Computers: New Horizons and Applications
- Principal Investigator
  
  Le Gall Francois
- Project Period (FY)
  2020 – 2023
- Research Category
  
  Grant-in-Aid for Scientific Research (B)
- Review Section
  
  Basic Section 60010:Theory of informatics-related
- Research Institution
  Nagoya University
Computational Complexity of Minimum Description Size Problems
- Principal Investigator
  
  Watanabe Osamu
- Project Period (FY)
  2018 – 2021
- Research Category
  
  Grant-in-Aid for Scientific Research (A)
- Review Section
  
  Medium-sized Section 60:Information science, computer engineering, and related fields
- Research Institution
  Tokyo Institute of Technology

All 2023 2022 2021 2020 2018

All Journal Article Presentation

[Journal Article] A Duality between One-Way Functions and Average-Case Symmetry of Information2023
- Author(s)
  Hirahara Shuichi、Ilango Rahul、Lu Zhenjian、Nanashima Mikito、Oliveira Igor C.
- Journal Title
  
  Proceedings of the 55th Annual ACM Symposium on Theory of Computing
  
  Volume: 55 Pages: 1039-1050
- DOI
  10.1145/3564246.3585138
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-23K19957, KAKENHI-PROJECT-22H00522, KAKENHI-PROJECT-20H04139
[Journal Article] Non-Black-Box Worst-Case to Average-Case Reductions Within NP2023
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  SIAM Journal on Computing
  
  Volume: 52 Issue: 6 Pages: FOCS18-349-FOCS18-382
- DOI
  10.1137/19m124705x
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Cryptographic hardness under projections for time-bounded Kolmogorov complexity2023
- Author(s)
  Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
- Journal Title
  
  Theoretical Computer Science
  
  Volume: 940 Pages: 206-224
- DOI
  10.1016/j.tcs.2022.10.040
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Learning Versus Pseudorandom Generators in Constant Parallel Time2023
- Author(s)
  Shuichi Hirahara, Mikito Nanashima
- Journal Title
  
  Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Hardness Self-Amplification: Simplified, Optimized, and Unified2023
- Author(s)
  Hirahara Shuichi、Shimizu Nobutaka
- Journal Title
  
  Symposium on Theory of Computing
  
  Volume: 1 Pages: 70-83
- DOI
  10.1145/3564246.3585189
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-23K16837, KAKENHI-PROJECT-20H04139
[Journal Article] Kolmogorov Complexity Characterizes Statistical Zero Knowledge2023
- Author(s)
  Eric Allender, Shuichi Hirahara, Harsha Tirumala
- Journal Title
  
  Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Hardness Self-Amplification from Feasible Hard-Core Sets2022
- Author(s)
  Shuichi Hirahara, Nobutaka Shimizu
- Journal Title
  
  Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022)
  
  Volume: - Pages: 543-554
- DOI
  10.1109/focs54457.2022.00058
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Excluding PH Pessiland2022
- Author(s)
  Shuichi Hirahara, Rahul Santhanam
- Journal Title
  
  Proc. of Innovations in Theoretical Computer Science Conference
  
  Volume: LIPIcs 215
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Excluding PH Pessiland2022
- Author(s)
  Shuichi Hirahara, Rahul Santhanam
- Journal Title
  
  Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] NP-Hardness of Learning Programs and Partial MCSP2022
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  Proceedings of the Symposium on Foundations of Computer Science (FOCS 2022)
  
  Volume: - Pages: 968-979
- DOI
  10.1109/focs54457.2022.00095
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions2022
- Author(s)
  Lijie Chen, Shuichi Hirahara, Neekon Vafa
- Journal Title
  
  Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Finding Errorless Pessiland in Error-Prone Heuristica2022
- Author(s)
  Shuichi Hirahara, Mikito Nanashima
- Journal Title
  
  Proceedings of the 37th Computational Complexity Conference (CCC 2022)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Symmetry of Information from Meta-Complexity2022
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  Proceedings of the 37th Computational Complexity Conference (CCC 2022)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Errorless Versus Error-Prone Average-Case Complexity2022
- Author(s)
  Shuichi Hirahara, Rahul Santhanam
- Journal Title
  
  Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] On Worst-Case Learning in Relativized Heuristica2022
- Author(s)
  Hirahara Shuichi、Nanashima Mikito
- Journal Title
  
  Proc. of the 62nd IEEE Annual Symposium on Foundations of Computer Science
  
  Volume: IEEE62 Pages: 751-758
- DOI
  10.1109/focs52979.2021.00078
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Average-Case hardness of NP and PH from worst-case fine-grained assumptions2022
- Author(s)
  Lijie Chen, Shuichi Hirahara, Neekon Vafa
- Journal Title
  
  Proc. of Innovations in Theoretical Computer Science Conference
  
  Volume: LIPIcs 215
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Hardness of Constant-round Communication Complexity2021
- Author(s)
  Shuichi Hirahara, Rahul Ilango, Bruno Loff
- Journal Title
  
  Proceedings of the 36th Computational Complexity Conference (CCC 2021
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH2021
- Author(s)
  Shuichi Hirahara, Nobutaka Shimizu
- Journal Title
  
  Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
  
  Volume: - Pages: 2346-2365
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH2021
- Author(s)
  Hirahara Shuichi、Shimizu Nobutaka
- Journal Title
  
  Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms
  
  Volume: SODA21 Pages: 2346-2365
- DOI
  10.1137/1.9781611976465.140
- ISBN
  9781611976465
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity2021
- Author(s)
  Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
- Journal Title
  
  Proc. of the 32nd International Symposium on Algorithms and Computation
  
  Volume: LIPIcs212
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Average-case hardness of NP from exponential worst-case hardness assumptions2021
- Author(s)
  Hirahara Shuichi
- Journal Title
  
  Proc. of the 53rd Annual ACM Symposium on Theory of Computing
  
  Volume: ACM53 Pages: 292-302
- DOI
  10.1145/3406325.3451065
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-18H04090, KAKENHI-PROJECT-20H04139
[Journal Article] Test of Quantumness with Small-Depth Quantum Circuits2021
- Author(s)
  Shuichi Hirahara and Francois Le Gall
- Journal Title
  
  Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity2021
- Author(s)
  Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
- Journal Title
  
  Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] One-tape Turing machine and branching program lower bounds for MCSP2021
- Author(s)
  Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
- Journal Title
  
  Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science
  
  Volume: -
- Peer Reviewed / Open Access / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] Unexpected hardness results for Kolmogorov complexity under uniform reductions2020
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  in Proc. ACM STOC 2020
  
  Volume: ACM Pages: 1038-1051
- DOI
  10.1145/3357713.3384251
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-18H04090, KAKENHI-PROJECT-20H04139
[Journal Article] Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions2020
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  in Proc. CCC 2020
  
  Volume: LIPIcs 169
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions2020
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  Proceedings of the 35th Computational Complexity Conference (CCC 2020)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets2020
- Author(s)
  Hirahara Shuichi、Watanabe Osamu
- Journal Title
  
  Complexity and Approximation - In Memory of Ker-I Ko
  
  Volume: LNCS 12000 Pages: 67-79
- DOI
  10.1007/978-3-030-41672-0_6
- ISBN
  9783030416713, 9783030416720
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] On Nonadaptive Security Reductions of Hitting Set Generators2020
- Author(s)
  Shuichi Hirahara, Osamu Watanabe
- Journal Title
  
  Proceedings of the International Conference on Randomization and Computation (RANDOM 2020)
  
  Volume: -
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-20H04139
[Journal Article] On nonadaptive security reductions of hitting set generators2020
- Author(s)
  Shuichi Hirahara and Osamu Watanabe
- Journal Title
  
  in Proc. APPROX/RANDOM 2020
  
  Volume: LIPIcs 176(15)
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-18H04090
[Journal Article] Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity2020
- Author(s)
  Hirahara Shuichi
- Journal Title
  
  in Proc. IEEE FOCS 2020
  
  Volume: IEEE Pages: 50-60
- DOI
  10.1109/focs46700.2020.00014
- Peer Reviewed / Open Access
- Data Source
  KAKENHI-PROJECT-18H04090, KAKENHI-PROJECT-20H04139
[Journal Article] Non-black-box worst-case to average-case reductions within NP2018
- Author(s)
  Shuichi Hirahara
- Journal Title
  
  Proc. of the 59th IEEE Annual Symposium on Foundations of Computer Science
  
  Volume: - Pages: 247-258
- DOI
  10.1109/focs.2018.00032
- Peer Reviewed
- Data Source
  KAKENHI-PROJECT-18H04090, KAKENHI-PROJECT-16J06743
[Presentation] Meta-complexity and average-case complexity2023
- Author(s)
  Shuichi Hirahara
- Organizer
  Computational Complexity Conference (CCC 2023)
- Invited / Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-20H04139
[Presentation] メタ計算量と平均時計算量2023
- Author(s)
  平原秀一
- Organizer
  コンピュテーション研究会（COMP）
- Invited
- Data Source
  KAKENHI-PROJECT-20H04139
[Presentation] NPの最悪時及び平均時計算量について2020
- Author(s)
  平原秀一
- Organizer
  電子情報通信学会総合大会 COMP学生シンポジウム
- Data Source
  KAKENHI-PROJECT-18H04090
[Presentation] Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits2020
- Author(s)
  Shinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi Yoshida
- Organizer
  Conference on Neural Information Processing Systems (NeurIPS 2020)
- Data Source
  KAKENHI-PROJECT-20H04139
[Presentation] NP-hardness of minimum circuit size problem for OR-AND-MOD circuits2018
- Author(s)
  Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam
- Organizer
  The 33rd Computational Complexity Conference
- Int'l Joint Research
- Data Source
  KAKENHI-PROJECT-18H04090

1. 清水伸高 (10910127)

# of Collaborated Projects: 2 results

# of Collaborated Products: 2 results
2. Watanabe Osamu (80158617)

# of Collaborated Projects: 1 results

# of Collaborated Products: 2 results
3. Le Gall Francois (50584299)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
4. 伊東利哉 (20184674)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results
5. 天野一幸 (30282031)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
6. 玉置卓 (40432413)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
7. 森立平 (60732857)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
8. 河原林健一 (40361159)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
9. 岩田覚 (00263161)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
10. 吉田悠一 (50636967)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
11. 福永拓郎 (60452314)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
12. Avis David (90584110)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
13. 泉泰介 (20432461)

# of Collaborated Projects: 1 results

# of Collaborated Products: 0 results
14. 七島幹人 (90855222)

# of Collaborated Projects: 1 results

# of Collaborated Products: 1 results

Hirahara Shuichi 平原 秀一

Research Projects

Research Products

Co-Researchers

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

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

New computational models for algorithms and discrete optimization

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Quantum Algorithms for Large-Scale Quantum Computers: New Horizons and Applications

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

Computational Complexity of Minimum Description Size Problems

Principal Investigator

Project Period (FY)

Research Category

Review Section

Research Institution

[Journal Article] A Duality between One-Way Functions and Average-Case Symmetry of Information2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Non-Black-Box Worst-Case to Average-Case Reductions Within NP2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Cryptographic hardness under projections for time-bounded Kolmogorov complexity2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Learning Versus Pseudorandom Generators in Constant Parallel Time2023

Author(s)

Journal Title

Data Source

[Journal Article] Hardness Self-Amplification: Simplified, Optimized, and Unified2023

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Kolmogorov Complexity Characterizes Statistical Zero Knowledge2023

Author(s)

Journal Title

Data Source

[Journal Article] Hardness Self-Amplification from Feasible Hard-Core Sets2022

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Excluding PH Pessiland2022

Author(s)

Journal Title

Data Source

[Journal Article] Excluding PH Pessiland2022

Author(s)

Journal Title

Data Source

[Journal Article] NP-Hardness of Learning Programs and Partial MCSP2022

Author(s)

Journal Title

DOI

Data Source

[Journal Article] Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions2022

Author(s)

Journal Title

Data Source

[Journal Article] Finding Errorless Pessiland in Error-Prone Heuristica2022

Author(s)

Hirahara Shuichi 平原秀一