HIRAHARA Shuichi

researchmap

Keyword

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

Papers (Latest 5)

• • Planted Clique Conjectures Are Equivalent.
  • DOI: 10.1145/3618260.3649751
  • Publish year: 2024
  • Journal: STOC
  • URL: https://researchmap.jp/shuichi.hirahara/published_papers/47178191
• • Beating Brute Force for Compression Problems.
  • DOI: 10.1145/3618260.3649778
  • Publish year: 2024
  • Journal: STOC
  • URL: https://researchmap.jp/shuichi.hirahara/published_papers/47178192
• • Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.
  • DOI: 10.1145/3618260.3649667
  • Publish year: 2024
  • Journal: STOC
  • URL: https://researchmap.jp/shuichi.hirahara/published_papers/47178193
• • 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

KAKEN (Principal Investigator)

Research Projects (Latest 5)

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

CiNii Articles (Latest 5)

• • 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: Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
  • URL: https://cir.nii.ac.jp/crid/1010861618231226379
• • 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
• • 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