Identifying an Honest EXP^NP Oracle Among Many. - Shuichi Hirahara (CCC, 2015)

Limits of Minimum Circuit Size Problem as Oracle. - Shuichi Hirahara; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2015)

On the Average-Case Complexity of MCSP and Its Variants. - Shuichi Hirahara; Rahul Santhanam (CCC, 2017)

Virtual machine placement for minimizing connection cost in data center networks. - Takuro Fukunaga; Shuichi Hirahara; Hiyori Yoshikawa (Discret. Optim., 2017)

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. - Eric Allender; Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2017)

A Duality Between Depth-Three Formulas and Approximation by Depth-Two. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2017)

On characterizations of randomized computation using plain Kolmogorov complexity. - Shuichi Hirahara; Akitoshi Kawamura (Comput., 2018)

Non-black-box Worst-case to Average-case Reductions within NP. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2018)

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. - Shuichi Hirahara; Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. - Shuichi Hirahara; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2019)

Beyond Natural Proofs: Hardness Magnification and Locality. - Igor Carboni Oliveira; Lijie Chen 001; Shuichi Hirahara; Ján Pich; Ninad Rajgopal; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2019)

On Nonadaptive Security Reductions of Hitting Set Generators. - Shuichi Hirahara; Osamu Watanabe 001 (APPROX-RANDOM, 2020)

Unexpected Power of Random Strings. - Shuichi Hirahara (ITCS, 2020)

Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits. - Shinji Ito; Shuichi Hirahara; Tasuku Soma; Yuichi Yoshida (NeurIPS, 2020)

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. - Mahdi Cheraghchi; Shuichi Hirahara; Dimitrios Myrisiotis; Yuichi Yoshida (Electron. Colloquium Comput. Complex., 2020)

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2020)

Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2020)

Test of Quantumness with Small-Depth Quantum Circuits. - Shuichi Hirahara; François Le Gall (MFCS, 2021)

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH. - Shuichi Hirahara; Nobutaka Shimizu (SODA, 2021)

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions. - Lijie Chen 001; Shuichi Hirahara; Neekon Vafa (Electron. Colloquium Comput. Complex., 2021)

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2021)

Hardness of Constant-round Communication Complexity. - Shuichi Hirahara; Rahul Ilango; Bruno Loff (Electron. Colloquium Comput. Complex., 2021)

On Worst-Case Learning in Relativized Heuristica. - Shuichi Hirahara; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2021)

Symmetry of Information from Meta-Complexity. - Shuichi Hirahara (CCC, 2022)

Finding Errorless Pessiland in Error-Prone Heuristica. - Shuichi Hirahara; Mikito Nanashima (CCC, 2022)

Errorless Versus Error-Prone Average-Case Complexity. - Shuichi Hirahara; Rahul Santhanam (ITCS, 2022)

Excluding PH Pessiland. - Shuichi Hirahara; Rahul Santhanam (ITCS, 2022)

Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica. - Shuichi Hirahara (Bull. EATCS, 2022)

Kolmogorov Complexity Characterizes Statistical Zero Knowledge. - Eric Allender; Shuichi Hirahara; Harsha Tirumala (Electron. Colloquium Comput. Complex., 2022)

NP-Hardness of Learning Programs and Partial MCSP. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2022)

Learning versus Pseudorandom Generators in Constant Parallel Time. - Shuichi Hirahara; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2022)

Hardness Self-Amplification from Feasible Hard-Core Sets. - Shuichi Hirahara; Nobutaka Shimizu (Electron. Colloquium Comput. Complex., 2022)

Regularization of Low Error PCPs and an Application to MCSP. - Shuichi Hirahara; Dana Moshkovitz (ISAAC, 2023)

Symmetric Exponential Time Requires Near-Maximum Circuit Size. - Lijie Chen 001; Shuichi Hirahara; Hanlin Ren (Electron. Colloquium Comput. Complex., 2023)

Capturing One-Way Functions via NP-Hardness of Meta-Complexity. - Shuichi Hirahara (Electron. Colloquium Comput. Complex., 2023)

Beating Brute Force for Compression Problems. - Shuichi Hirahara; Rahul Ilango; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2023)

A Duality Between One-Way Functions and Average-Case Symmetry of Information. - Shuichi Hirahara; Rahul Ilango; Zhenjian Lu; Mikito Nanashima; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2023)

Bounded Relativization. - Shuichi Hirahara; Zhenjian Lu; Hanlin Ren (Electron. Colloquium Comput. Complex., 2023)

Learning in Pessiland via Inductive Inference. - Shuichi Hirahara; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2023)

Hardness Self-Amplification: Simplified, Optimized, and Unified. - Shuichi Hirahara; Nobutaka Shimizu (Electron. Colloquium Comput. Complex., 2023)

Cryptographic hardness under projections for time-bounded Kolmogorov complexity. - Eric Allender; John Gouwar; Shuichi Hirahara; Caleb Robelle (Theor. Comput. Sci., 2023)

Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions. - Shuichi Hirahara (Theory Comput., 2023)

Non-Black-Box Worst-Case to Average-Case Reductions Within ( mathsf{NP} ). - Shuichi Hirahara (SIAM J. Comput., 2023)

Asymptotic Inapproximability of Reconfiguration Problems: Maxmin k-Cut and Maxmin Ek-SAT. - Shuichi Hirahara; Naoto Ohsaka (CoRR, 2024)

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. - Shuichi Hirahara; Valentine Kabanets; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. - Shuichi Hirahara; Zhenjian Lu; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2024)

One-Way Functions and pKt Complexity. - Shuichi Hirahara; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2024)

One-Way Functions and Zero Knowledge. - Shuichi Hirahara; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. - Shuichi Hirahara; Naoto Ohsaka (Electron. Colloquium Comput. Complex., 2024)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. - Shuichi Hirahara; Naoto Ohsaka (Electron. Colloquium Comput. Complex., 2024)

Planted Clique Conjectures Are Equivalent. - Shuichi Hirahara; Nobutaka Shimizu (Electron. Colloquium Comput. Complex., 2024)

Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration. - Shuichi Hirahara; Naoto Ohsaka (ICALP, 2025)

Communication Complexity is NP-hard. - Shuichi Hirahara; Rahul Ilango; Bruno Loff (Electron. Colloquium Comput. Complex., 2025)

Complexity-Theoretic Inductive Inference. - Shuichi Hirahara; Mikito Nanashima (Electron. Colloquium Comput. Complex., 2025)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration. - Shuichi Hirahara; Naoto Ohsaka (Electron. Colloquium Comput. Complex., 2025)

Error-Correction of Matrix Multiplication Algorithms. - Shuichi Hirahara; Nobutaka Shimizu (Electron. Colloquium Comput. Complex., 2025)

An Optimal Error-Correcting Reduction for Matrix Multiplication. - Shuichi Hirahara; Nobutaka Shimizu (Electron. Colloquium Comput. Complex., 2025)

Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration. - Shuichi Hirahara; Naoto Ohsaka (CoRR, 2025)