Shuichi Hirahara

116 papers A* 25A 18B 5Journal 63Unranked 5
YearRankTypeTitle / Venue / Authors
2026 J jnl
Symmetric Exponential Time Requires Near-Maximum Circuit Size.
J. ACM
Lijie Chen, Shuichi Hirahara, Zeyong Li, Hanlin Ren
2025 A* conf
An Optimal Error-Correcting Reduction for Matrix Multiplication.
ICALP
Shuichi Hirahara, Nobutaka Shimizu
2025 J jnl
An Optimal Error-Correcting Reduction for Matrix Multiplication.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Nobutaka Shimizu
2025 J jnl
Asymptotically Optimal Inapproximability of E
CoRR
Shuichi Hirahara, Naoto Ohsaka
2025 J jnl
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Naoto Ohsaka
2025 A* conf
Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration.
FOCS
Shuichi Hirahara, Naoto Ohsaka
2025 A* conf
Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration.
ICALP
Shuichi Hirahara, Naoto Ohsaka
2025 J jnl
Communication Complexity is NP-hard.
CoRR
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 J jnl
Communication Complexity is NP-hard.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2025 J jnl
Complexity-Theoretic Inductive Inference.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Mikito Nanashima
2025 A* conf
Error-Correction of Matrix Multiplication Algorithms.
STOC
Shuichi Hirahara, Nobutaka Shimizu
2025 J jnl
Error-Correction of Matrix Multiplication Algorithms.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Nobutaka Shimizu
2025 A* conf
NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions.
FOCS
Shuichi Hirahara, Rahul Ilango
2025 B conf
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules.
ISAAC
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou
2025 J jnl
Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules.
CoRR
Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou
2024 J jnl
Asymptotic Inapproximability of Reconfiguration Problems: Maxmin
CoRR
Shuichi Hirahara, Naoto Ohsaka
2024 A* conf
Beating Brute Force for Compression Problems.
STOC
Shuichi Hirahara, Rahul Ilango, R. Ryan Williams
2024 A conf
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.
CCC
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
Theory Comput. Syst.
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2024 A* conf
One-Way Functions and Zero Knowledge.
STOC
Shuichi Hirahara, Mikito Nanashima
2024 J jnl
One-Way Functions and Zero Knowledge.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Mikito Nanashima
2024 — conf
One-Way Functions and pKt Complexity.
TCC (1)
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 A* conf
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
FOCS
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2024 J jnl
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
CoRR
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2024 J jnl
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima
2024 A* conf
Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration.
ICALP
Shuichi Hirahara, Naoto Ohsaka
2024 J jnl
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration.
CoRR
Shuichi Hirahara, Naoto Ohsaka
2024 J jnl
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Naoto Ohsaka
2024 A* conf
Planted Clique Conjectures Are Equivalent.
STOC
Shuichi Hirahara, Nobutaka Shimizu
2024 J jnl
Planted Clique Conjectures Are Equivalent.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Nobutaka Shimizu
2024 A* conf
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.
STOC
Shuichi Hirahara, Naoto Ohsaka
2024 J jnl
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.
CoRR
Shuichi Hirahara, Naoto Ohsaka
2024 J jnl
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Naoto Ohsaka
2024 A* conf
Symmetric Exponential Time Requires Near-Maximum Circuit Size.
STOC
Lijie Chen, Shuichi Hirahara, Hanlin Ren
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 A* conf
A Duality between One-Way Functions and Average-Case Symmetry of Information.
STOC
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 J jnl
Beating Brute Force for Compression Problems.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Ryan Williams
2023 A conf
Bounded Relativization.
CCC
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
2023 J jnl
Bounded Relativization.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren
2023 A* conf
Capturing One-Way Functions via NP-Hardness of Meta-Complexity.
STOC
Shuichi Hirahara
2023 J jnl
Capturing One-Way Functions via NP-Hardness of Meta-Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2023 J jnl
Cryptographic hardness under projections for time-bounded Kolmogorov complexity.
Theor. Comput. Sci.
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2023 A* conf
Hardness Self-Amplification: Simplified, Optimized, and Unified.
STOC
Shuichi Hirahara, Nobutaka Shimizu
2023 J jnl
Hardness Self-Amplification: Simplified, Optimized, and Unified.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Nobutaka Shimizu
2023 A conf
Kolmogorov Complexity Characterizes Statistical Zero Knowledge.
ITCS
Eric Allender, Shuichi Hirahara, Harsha Tirumala
2023 A conf
Learning Versus Pseudorandom Generators in Constant Parallel Time.
ITCS
Shuichi Hirahara, Mikito Nanashima
2023 A* conf
Learning in Pessiland via Inductive Inference.
FOCS
Shuichi Hirahara, Mikito Nanashima
2023 J jnl
Learning in Pessiland via Inductive Inference.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Mikito Nanashima
2023 J jnl
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\).
SIAM J. Comput.
Shuichi Hirahara
2023 J jnl
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions.
Theory Comput.
Shuichi Hirahara
2023 B conf
Regularization of Low Error PCPs and an Application to MCSP.
ISAAC
Shuichi Hirahara, Dana Moshkovitz
2023 J jnl
Symmetric Exponential Time Requires Near-Maximum Circuit Size.
CoRR
Lijie Chen, Shuichi Hirahara, Hanlin Ren
2023 J jnl
Symmetric Exponential Time Requires Near-Maximum Circuit Size.
Electron. Colloquium Comput. Complex.
Lijie Chen, Shuichi Hirahara, Hanlin Ren
2022 A conf
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions.
ITCS
Lijie Chen, Shuichi Hirahara, Neekon Vafa
2022 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
J. ACM
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2022 A conf
Errorless Versus Error-Prone Average-Case Complexity.
ITCS
Shuichi Hirahara, Rahul Santhanam
2022 A conf
Excluding PH Pessiland.
ITCS
Shuichi Hirahara, Rahul Santhanam
2022 A conf
Finding Errorless Pessiland in Error-Prone Heuristica.
CCC
Shuichi Hirahara, Mikito Nanashima
2022 A* conf
Hardness Self-Amplification from Feasible Hard-Core Sets.
FOCS
Shuichi Hirahara, Nobutaka Shimizu
2022 J jnl
Hardness Self-Amplification from Feasible Hard-Core Sets.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Nobutaka Shimizu
2022 J jnl
Kolmogorov Complexity Characterizes Statistical Zero Knowledge.
Electron. Colloquium Comput. Complex.
Eric Allender, Shuichi Hirahara, Harsha Tirumala
2022 J jnl
Learning versus Pseudorandom Generators in Constant Parallel Time.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Mikito Nanashima
2022 J jnl
Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica.
Bull. EATCS
Shuichi Hirahara
2022 A* conf
NP-Hardness of Learning Programs and Partial MCSP.
FOCS
Shuichi Hirahara
2022 J jnl
NP-Hardness of Learning Programs and Partial MCSP.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2022 A conf
Symmetry of Information from Meta-Complexity.
CCC
Shuichi Hirahara
2021 J jnl
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2021 J jnl
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions.
Electron. Colloquium Comput. Complex.
Lijie Chen, Shuichi Hirahara, Neekon Vafa
2021 A* conf
Average-case hardness of NP from exponential worst-case hardness assumptions.
STOC
Shuichi Hirahara
2021 B conf
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity.
ISAAC
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2021 J jnl
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle
2021 A conf
Hardness of Constant-Round Communication Complexity.
CCC
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 J jnl
Hardness of Constant-round Communication Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Bruno Loff
2021 A* conf
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH.
SODA
Shuichi Hirahara, Nobutaka Shimizu
2021 A* conf
On Worst-Case Learning in Relativized Heuristica.
FOCS
Shuichi Hirahara, Mikito Nanashima
2021 J jnl
On Worst-Case Learning in Relativized Heuristica.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Mikito Nanashima
2021 A conf
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
STACS
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2021 B conf
Test of Quantumness with Small-Depth Quantum Circuits.
MFCS
Shuichi Hirahara, François Le Gall
2021 J jnl
Test of Quantumness with Small-Depth Quantum Circuits.
CoRR
Shuichi Hirahara, François Le Gall
2020 A conf
Beyond Natural Proofs: Hardness Magnification and Locality.
ITCS
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2020 A* conf
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity.
FOCS
Shuichi Hirahara
2020 J jnl
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2020 J jnl
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH.
CoRR
Shuichi Hirahara, Nobutaka Shimizu
2020 A conf
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions.
CCC
Shuichi Hirahara
2020 — conf
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Complexity and Approximation
Shuichi Hirahara, Osamu Watanabe
2020 — conf
On Nonadaptive Security Reductions of Hitting Set Generators.
APPROX-RANDOM
Shuichi Hirahara, Osamu Watanabe
2020 J jnl
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
2020 A* conf
Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits.
NeurIPS
Shinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi Yoshida
2020 J jnl
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2020 A conf
Unexpected Power of Random Strings.
ITCS
Shuichi Hirahara
2020 A* conf
Unexpected hardness results for Kolmogorov complexity under uniform reductions.
STOC
Shuichi Hirahara
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
CoRR
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems.
ACM Trans. Comput. Theory
Eric Allender, Shuichi Hirahara
2019 J jnl
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Osamu Watanabe
2018 A conf
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
CCC
Shuichi Hirahara, Igor C. Oliveira, Rahul Santhanam
2018 J jnl
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
2018 A* conf
Non-Black-Box Worst-Case to Average-Case Reductions within NP.
FOCS
Shuichi Hirahara
2018 J jnl
Non-black-box Worst-case to Average-case Reductions within NP.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2018 J jnl
On characterizations of randomized computation using plain Kolmogorov complexity.
Comput.
Shuichi Hirahara, Akitoshi Kawamura
2017 J jnl
A Duality Between Depth-Three Formulas and Approximation by Depth-Two.
CoRR
Shuichi Hirahara
2017 J jnl
A Duality Between Depth-Three Formulas and Approximation by Depth-Two.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara
2017 J jnl
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems.
Electron. Colloquium Comput. Complex.
Eric Allender, Shuichi Hirahara
2017 B conf
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems.
MFCS
Eric Allender, Shuichi Hirahara
2017 A conf
On the Average-Case Complexity of MCSP and Its Variants.
CCC
Shuichi Hirahara, Rahul Santhanam
2017 J jnl
Virtual machine placement for minimizing connection cost in data center networks.
Discret. Optim.
Takuro Fukunaga, Shuichi Hirahara, Hiyori Yoshikawa
2016 A conf
Limits of Minimum Circuit Size Problem as Oracle.
CCC
Shuichi Hirahara, Osamu Watanabe
2015 A conf
Identifying an Honest EXP^NP Oracle Among Many.
CCC
Shuichi Hirahara
2015 J jnl
Identifying an Honest EXP^NP Oracle Among Many.
CoRR
Shuichi Hirahara
2015 J jnl
Limits of Minimum Circuit Size Problem as Oracle.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Osamu Watanabe
2015 — conf
Virtual machine placement for minimizing connection cost in data center networks.
INFOCOM Workshops
Takuro Fukunaga, Shuichi Hirahara, Hiyori Yoshikawa
2014 — conf
On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity.
MFCS (2)
Shuichi Hirahara, Akitoshi Kawamura