Shuichi Hirahara

According to our database, Shuichi Hirahara authored at least 51 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Planted Clique Conjectures Are Equivalent.

Shuichi Hirahara, Nobutaka Shimizu

Electron. Colloquium Comput. Complex., 2024

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration.

Shuichi Hirahara, Naoto Ohsaka

Electron. Colloquium Comput. Complex., 2024

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.

Shuichi Hirahara, Naoto Ohsaka

Electron. Colloquium Comput. Complex., 2024

One-Way Functions and Zero Knowledge.

Shuichi Hirahara, Mikito Nanashima

Electron. Colloquium Comput. Complex., 2024

One-Way Functions and pKt Complexity.

Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira

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

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2024

Asymptotic Inapproximability of Reconfiguration Problems: Maxmin <i>k</i>-Cut and Maxmin E<i>k</i>-SAT.

Shuichi Hirahara, Naoto Ohsaka

CoRR, 2024

2023

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\).

Shuichi Hirahara

SIAM J. Comput., December, 2023

Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions.

Shuichi Hirahara

Theory Comput., 2023

Cryptographic hardness under projections for time-bounded Kolmogorov complexity.

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

Theor. Comput. Sci., 2023

Hardness Self-Amplification: Simplified, Optimized, and Unified.

Shuichi Hirahara, Nobutaka Shimizu

Electron. Colloquium Comput. Complex., 2023

Learning in Pessiland via Inductive Inference.

Shuichi Hirahara, Mikito Nanashima

Electron. Colloquium Comput. Complex., 2023

Bounded Relativization.

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

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

Beating Brute Force for Compression Problems.

Shuichi Hirahara, Rahul Ilango, Ryan Williams

Electron. Colloquium Comput. Complex., 2023

Capturing One-Way Functions via NP-Hardness of Meta-Complexity.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2023

Symmetric Exponential Time Requires Near-Maximum Circuit Size.

Lijie Chen, Shuichi Hirahara, Hanlin Ren

Electron. Colloquium Comput. Complex., 2023

Regularization of Low Error PCPs and an Application to MCSP.

Shuichi Hirahara, Dana Moshkovitz

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Hardness Self-Amplification from Feasible Hard-Core Sets.

Shuichi Hirahara, Nobutaka Shimizu

Electron. Colloquium Comput. Complex., 2022

Learning versus Pseudorandom Generators in Constant Parallel Time.

Shuichi Hirahara, Mikito Nanashima

Electron. Colloquium Comput. Complex., 2022

NP-Hardness of Learning Programs and Partial MCSP.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2022

Kolmogorov Complexity Characterizes Statistical Zero Knowledge.

Eric Allender, Shuichi Hirahara, Harsha Tirumala

Electron. Colloquium Comput. Complex., 2022

Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica.

Shuichi Hirahara

Bull. EATCS, 2022

Excluding PH Pessiland.

Shuichi Hirahara, Rahul Santhanam

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Errorless Versus Error-Prone Average-Case Complexity.

Shuichi Hirahara, Rahul Santhanam

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Finding Errorless Pessiland in Error-Prone Heuristica.

Shuichi Hirahara, Mikito Nanashima

Proceedings of the 37th Computational Complexity Conference, 2022

Symmetry of Information from Meta-Complexity.

Shuichi Hirahara

Proceedings of the 37th Computational Complexity Conference, 2022

2021

On Worst-Case Learning in Relativized Heuristica.

Shuichi Hirahara, Mikito Nanashima

Electron. Colloquium Comput. Complex., 2021

Hardness of Constant-round Communication Complexity.

Shuichi Hirahara, Rahul Ilango, Bruno Loff

Electron. Colloquium Comput. Complex., 2021

Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2021

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions.

Lijie Chen, Shuichi Hirahara, Neekon Vafa

Electron. Colloquium Comput. Complex., 2021

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Test of Quantumness with Small-Depth Quantum Circuits.

Shuichi Hirahara, François Le Gall

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2020

Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 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

Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits.

Shinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi Yoshida

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Unexpected Power of Random Strings.

Shuichi Hirahara

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

On Nonadaptive Security Reductions of Hitting Set Generators.

Shuichi Hirahara, Osamu Watanabe

Proceedings of the Approximation, 2020

2019

Beyond Natural Proofs: Hardness Magnification and Locality.

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2019

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.

Shuichi Hirahara, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2019

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

Non-black-box Worst-case to Average-case Reductions within NP.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2018

On characterizations of randomized computation using plain Kolmogorov complexity.

Shuichi Hirahara, Akitoshi Kawamura

Comput., 2018

2017

A Duality Between Depth-Three Formulas and Approximation by Depth-Two.

Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2017

New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems.

Eric Allender, Shuichi Hirahara

Electron. Colloquium Comput. Complex., 2017

Virtual machine placement for minimizing connection cost in data center networks.

Takuro Fukunaga, Shuichi Hirahara, Hiyori Yoshikawa

Discret. Optim., 2017

On the Average-Case Complexity of MCSP and Its Variants.

Shuichi Hirahara, Rahul Santhanam

Proceedings of the 32nd Computational Complexity Conference, 2017

2015

Limits of Minimum Circuit Size Problem as Oracle.

Shuichi Hirahara, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2015

Identifying an Honest EXP^NP Oracle Among Many.

Shuichi Hirahara

Proceedings of the 30th Conference on Computational Complexity, 2015