Shuichi Hirahara

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 88

Top Topics

Kolmogorov Complexity

Inductive Inference

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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