Shuichi Hirahara

ScholarGPS® ID: 79214912997558

Affiliation

National Institute of Informatics, Japan

Affiliation History

Field

Engineering and Computer Science

Discipline

Computer Science

Top Specialties

Virtual Machine

Metrics Summary

Publication Count

Predicted Citations

157

Predicted h-index

Ranking

Publications and Citation History

Publications based on Top Specialties

Types of Publication

Publications
Books
Patents
NIH/NSF

Add Delete
One-Way Functions and Zero Knowledge (conference) Hirahara, Shuichi \| Nanashima, Mikito STOC '24: 56th Annual ACM Symposium on Theory of Computing (2024) Vancouver BC Canada 10.1145/3618260.3649701 Cite \| Source
Beating Brute Force for Compression Problems (conference) Hirahara, Shuichi \| Ilango, Rahul \| Williams, R. Ryan STOC '24: 56th Annual ACM Symposium on Theory of Computing (2024) Vancouver BC Canada 10.1145/3618260.3649778 Cite \| Source
Planted Clique Conjectures Are Equivalent (conference) Hirahara, Shuichi \| Shimizu, Nobutaka STOC '24: 56th Annual ACM Symposium on Theory of Computing (2024) Vancouver BC Canada 10.1145/3618260.3649751 Cite \| Source
Symmetric Exponential Time Requires Near-Maximum Circuit Size (conference) Chen, Lijie \| Hirahara, Shuichi \| Ren, Hanlin STOC '24: 56th Annual ACM Symposium on Theory of Computing (2024) Vancouver BC Canada 10.1145/3618260.3649624 Cite \| Source
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (journal article) Hirahara, Shuichi SIAM Journal on Computing, volume 52, issue 6, pages FOCS18-349-FOCS18-382 (2023). 10.1137/19M124705X Cite \| Source
Learning in Pessiland via Inductive Inference (conference) Hirahara, Shuichi \| Nanashima, Mikito 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023) Santa Cruz, CA, USA 10.1109/FOCS57990.2023.00033 Cited by (1) \| Cite \| Source
Hardness Self-Amplification: Simplified, Optimized, and Unified (conference) Hirahara, Shuichi \| Shimizu, Nobutaka STOC '23: 55th Annual ACM Symposium on Theory of Computing (2023) Orlando FL USA 10.1145/3564246.3585189 Cited by (1) \| Cite \| Source
A Duality between One-Way Functions and Average-Case Symmetry of Information (conference) Hirahara, Shuichi \| Ilango, Rahul \| Lu, Zhenjian \| Nanashima, Mikito \| Oliveira, Igor C. STOC '23: 55th Annual ACM Symposium on Theory of Computing (2023) Orlando FL USA 10.1145/3564246.3585138 Cited by (1) \| Cite \| Source
Cryptographic hardness under projections for time-bounded Kolmogorov complexity (journal article) Allender, Eric \| Gouwar, John \| Hirahara, Shuichi \| Robelle, Caleb Theoretical Computer Science, volume 940 (2023). 10.1016/j.tcs.2022.10.040 Cite \| Source
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP (journal article) Cheraghchi, Mahdi \| Hirahara, Shuichi \| Myrisiotis, Dimitrios \| Yoshida, Yuichi Theory of Computing Systems (2022). 10.1007/s00224-022-10113-9 Cite \| Source
NP-Hardness of Learning Programs and Partial MCSP (conference) Hirahara, Shuichi 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022) Denver, CO, USA 10.1109/FOCS54457.2022.00095 Cited by (9) \| Cite \| Source
Hardness Self-Amplification from Feasible Hard-Core Sets (conference) Hirahara, Shuichi \| Shimizu, Nobutaka 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022) Denver, CO, USA 10.1109/FOCS54457.2022.00058 Cited by (2) \| Cite \| Source
Beyond Natural Proofs: Hardness Magnification and Locality (journal article) Chen, Lijie \| Hirahara, Shuichi \| Oliveira, Igor Carboni \| Pich, Ján \| Rajgopal, Ninad \| Santhanam, Rahul Journal of the ACM, volume 69, issue 4, pages 1-49 (2022). 10.1145/3538391 Cited by (3) \| Cite \| Source
On Worst-Case Learning in Relativized Heuristica (conference) Hirahara, Shuichi \| Nanashima, Mikito 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2022) Denver, CO, USA 10.1109/FOCS52979.2021.00078 Cited by (4) \| Cite \| Source
Average-case hardness of NP from exponential worst-case hardness assumptions (conference) Hirahara, Shuichi STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) Virtual Italy 10.1145/3406325.3451065 Cited by (7) \| Cite \| Source
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH (book chapter) In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) Hirahara, Shuichi \| Shimizu, Nobutaka Society for Industrial and Applied Mathematics (2021) 10.1137/1.9781611976465.140 Cited by (5) \| Cite \| Source
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity (conference) Hirahara, Shuichi 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020) Durham, NC, USA 10.1109/FOCS46700.2020.00014 Cited by (4) \| Cite \| Source
Unexpected hardness results for Kolmogorov complexity under uniform reductions (conference) Hirahara, Shuichi STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing (2020) Chicago IL USA 10.1145/3357713.3384251 Cited by (8) \| Cite \| Source
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets (book chapter) In Complexity and Approximation Hirahara, Shuichi \| Watanabe, Osamu Springer International Publishing (2020) 10.1007/978-3-030-41672-0_6 Cited by (1) \| Cite \| Source
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems (journal article) Allender, Eric \| Hirahara, Shuichi ACM Transactions on Computation Theory, volume 11, issue 4, pages 1-27 (2019). 10.1145/3349616 Cited by (13) \| Cite \| Source