default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDShuichi Hirahara
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j8]Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis
, Yuichi Yoshida:
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. Theory Comput. Syst. 68(4): 868-899 (2024)- [c45]Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. CCC 2024: 29:1-29:56 - [c44]Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration. ICALP 2024: 85:1-85:18 - [c43]Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. STOC 2024: 358-366 - [c42]Shuichi Hirahara, Rahul Ilango, R. Ryan Williams:
Beating Brute Force for Compression Problems. STOC 2024: 659-670 - [c41]Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. STOC 2024: 1435-1445 - [c40]Shuichi Hirahara, Mikito Nanashima:
One-Way Functions and Zero Knowledge. STOC 2024: 1731-1738 - [c39]Lijie Chen, Shuichi Hirahara, Hanlin Ren:
Symmetric Exponential Time Requires Near-Maximum Circuit Size. STOC 2024: 1990-1999 - [i44]Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. CoRR abs/2401.00474 (2024) - [i43]Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. CoRR abs/2402.12645 (2024) - [i42]Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima:
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. CoRR abs/2409.12744 (2024) - [i41]Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR24 (2024) - [i40]Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima:
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. Electron. Colloquium Comput. Complex. TR24 (2024) - [i39]Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira:
One-Way Functions and pKt Complexity. Electron. Colloquium Comput. Complex. TR24 (2024) - [i38]Shuichi Hirahara, Mikito Nanashima:
One-Way Functions and Zero Knowledge. Electron. Colloquium Comput. Complex. TR24 (2024) - [i37]Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. Electron. Colloquium Comput. Complex. TR24 (2024) - [i36]Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. Electron. Colloquium Comput. Complex. TR24 (2024) - [i35]Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. Electron. Colloquium Comput. Complex. TR24 (2024) - [i34]Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira:
One-Way Functions and pKt Complexity. IACR Cryptol. ePrint Arch. 2024: 1388 (2024) - 2023
- [j7]Shuichi Hirahara:
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\). SIAM J. Comput. 52(6): S18-349 (2023) - [j6]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic hardness under projections for time-bounded Kolmogorov complexity. Theor. Comput. Sci. 940(Part): 206-224 (2023) - [c38]Shuichi Hirahara, Zhenjian Lu, Hanlin Ren:
Bounded Relativization. CCC 2023: 6:1-6:45 - [c37]Shuichi Hirahara, Mikito Nanashima:
Learning in Pessiland via Inductive Inference. FOCS 2023: 447-457 - [c36]Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. ITCS 2023: 3:1-3:19 - [c35]Shuichi Hirahara, Mikito Nanashima:
Learning Versus Pseudorandom Generators in Constant Parallel Time. ITCS 2023: 70:1-70:18 - [c34]Shuichi Hirahara, Dana Moshkovitz:
Regularization of Low Error PCPs and an Application to MCSP. ISAAC 2023: 39:1-39:16 - [c33]Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification: Simplified, Optimized, and Unified. STOC 2023: 70-83 - [c32]Shuichi Hirahara:
Capturing One-Way Functions via NP-Hardness of Meta-Complexity. STOC 2023: 1027-1038 - [c31]Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira:
A Duality between One-Way Functions and Average-Case Symmetry of Information. STOC 2023: 1039-1050 - [i33]Lijie Chen, Shuichi Hirahara, Hanlin Ren:
Symmetric Exponential Time Requires Near-Maximum Circuit Size. CoRR abs/2309.12912 (2023) - [i32]Lijie Chen, Shuichi Hirahara, Hanlin Ren:
Symmetric Exponential Time Requires Near-Maximum Circuit Size. Electron. Colloquium Comput. Complex. TR23 (2023) - [i31]Shuichi Hirahara:
Capturing One-Way Functions via NP-Hardness of Meta-Complexity. Electron. Colloquium Comput. Complex. TR23 (2023) - [i30]Shuichi Hirahara, Rahul Ilango, Ryan Williams:
Beating Brute Force for Compression Problems. Electron. Colloquium Comput. Complex. TR23 (2023) - [i29]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. TR23 (2023) - [i28]Shuichi Hirahara, Zhenjian Lu, Hanlin Ren:
Bounded Relativization. Electron. Colloquium Comput. Complex. TR23 (2023) - [i27]Shuichi Hirahara, Mikito Nanashima:
Learning in Pessiland via Inductive Inference. Electron. Colloquium Comput. Complex. TR23 (2023) - [i26]Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification: Simplified, Optimized, and Unified. Electron. Colloquium Comput. Complex. TR23 (2023) - [i25]Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira:
A Duality Between One-Way Functions and Average-Case Symmetry of Information. IACR Cryptol. ePrint Arch. 2023: 424 (2023) - 2022
- [j5]Shuichi Hirahara:
Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica. Bull. EATCS 136 (2022) - [j4]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): 25:1-25:49 (2022) - [c30]Shuichi Hirahara, Mikito Nanashima:
Finding Errorless Pessiland in Error-Prone Heuristica. CCC 2022: 25:1-25:28 - [c29]Shuichi Hirahara:
Symmetry of Information from Meta-Complexity. CCC 2022: 26:1-26:41 - [c28]Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification from Feasible Hard-Core Sets. FOCS 2022: 543-554 - [c27]Shuichi Hirahara:
NP-Hardness of Learning Programs and Partial MCSP. FOCS 2022: 968-979 - [c26]Lijie Chen, Shuichi Hirahara, Neekon Vafa:
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. ITCS 2022: 45:1-45:16 - [c25]Shuichi Hirahara, Rahul Santhanam:
Errorless Versus Error-Prone Average-Case Complexity. ITCS 2022: 84:1-84:23 - [c24]Shuichi Hirahara, Rahul Santhanam:
Excluding PH Pessiland. ITCS 2022: 85:1-85:25 - [i24]Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. Electron. Colloquium Comput. Complex. TR22 (2022) - [i23]Shuichi Hirahara:
NP-Hardness of Learning Programs and Partial MCSP. Electron. Colloquium Comput. Complex. TR22 (2022) - [i22]Shuichi Hirahara, Mikito Nanashima:
Learning versus Pseudorandom Generators in Constant Parallel Time. Electron. Colloquium Comput. Complex. TR22 (2022) - [i21]Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification from Feasible Hard-Core Sets. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c23]Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Hardness of Constant-Round Communication Complexity. CCC 2021: 31:1-31:30 - [c22]Shuichi Hirahara, Mikito Nanashima:
On Worst-Case Learning in Relativized Heuristica. FOCS 2021: 751-758 - [c21]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. ISAAC 2021: 54:1-54:17 - [c20]Shuichi Hirahara, François Le Gall:
Test of Quantumness with Small-Depth Quantum Circuits. MFCS 2021: 59:1-59:15 - [c19]Shuichi Hirahara, Nobutaka Shimizu:
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH. SODA 2021: 2346-2365 - [c18]Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida:
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. STACS 2021: 23:1-23:19 - [c17]Shuichi Hirahara:
Average-case hardness of NP from exponential worst-case hardness assumptions. STOC 2021: 292-302 - [i20]Shuichi Hirahara, François Le Gall:
Test of Quantumness with Small-Depth Quantum Circuits. CoRR abs/2105.05500 (2021) - [i19]Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle:
Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i18]Lijie Chen, Shuichi Hirahara, Neekon Vafa:
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions. Electron. Colloquium Comput. Complex. TR21 (2021) - [i17]Shuichi Hirahara:
Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions. Electron. Colloquium Comput. Complex. TR21 (2021) - [i16]Shuichi Hirahara, Rahul Ilango, Bruno Loff:
Hardness of Constant-round Communication Complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i15]Shuichi Hirahara, Mikito Nanashima:
On Worst-Case Learning in Relativized Heuristica. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c16]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Security Reductions of Hitting Set Generators. APPROX-RANDOM 2020: 15:1-15:14 - [c15]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Complexity and Approximation 2020: 67-79 - [c14]Shuichi Hirahara:
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions. CCC 2020: 20:1-20:47 - [c13]Shuichi Hirahara:
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. FOCS 2020: 50-60 - [c12]Shuichi Hirahara:
Unexpected Power of Random Strings. ITCS 2020: 41:1-41:13 - [c11]Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam:
Beyond Natural Proofs: Hardness Magnification and Locality. ITCS 2020: 70:1-70:48 - [c10]Shinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi Yoshida:
Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits. NeurIPS 2020 - [c9]Shuichi Hirahara:
Unexpected hardness results for Kolmogorov complexity under uniform reductions. STOC 2020: 1038-1051 - [i14]Shuichi Hirahara, Nobutaka Shimizu:
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH. CoRR abs/2010.05822 (2020) - [i13]Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida:
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. Electron. Colloquium Comput. Complex. TR20 (2020) - [i12]Shuichi Hirahara:
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions. Electron. Colloquium Comput. Complex. TR20 (2020) - [i11]Shuichi Hirahara:
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j3]Eric Allender, Shuichi Hirahara:
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. ACM Trans. Comput. Theory 11(4): 27:1-27:27 (2019) - [i10]Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam:
Beyond Natural Proofs: Hardness Magnification and Locality. CoRR abs/1911.08297 (2019) - [i9]Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. Electron. Colloquium Comput. Complex. TR19 (2019) - [i8]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. TR19 (2019) - 2018
- [j2]Shuichi Hirahara, Akitoshi Kawamura:
On characterizations of randomized computation using plain Kolmogorov complexity. Comput. 7(1): 45-56 (2018) - [c8]Shuichi Hirahara, Igor C. Oliveira, Rahul Santhanam:
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. CCC 2018: 5:1-5:31 - [c7]Shuichi Hirahara:
Non-Black-Box Worst-Case to Average-Case Reductions within NP. FOCS 2018: 247-258 - [i7]Shuichi Hirahara:
Non-black-box Worst-case to Average-case Reductions within NP. Electron. Colloquium Comput. Complex. TR18 (2018) - [i6]Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam:
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j1]Takuro Fukunaga, Shuichi Hirahara, Hiyori Yoshikawa:
Virtual machine placement for minimizing connection cost in data center networks. Discret. Optim. 26: 183-198 (2017) - [c6]Shuichi Hirahara, Rahul Santhanam:
On the Average-Case Complexity of MCSP and Its Variants. CCC 2017: 7:1-7:20 - [c5]Eric Allender, Shuichi Hirahara:
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. MFCS 2017: 54:1-54:14 - [i5]Shuichi Hirahara:
A Duality Between Depth-Three Formulas and Approximation by Depth-Two. CoRR abs/1705.03588 (2017) - [i4]Eric Allender, Shuichi Hirahara:
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i3]Shuichi Hirahara:
A Duality Between Depth-Three Formulas and Approximation by Depth-Two. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c4]Shuichi Hirahara, Osamu Watanabe:
Limits of Minimum Circuit Size Problem as Oracle. CCC 2016: 18:1-18:20 - 2015
- [c3]Shuichi Hirahara:
Identifying an Honest EXP^NP Oracle Among Many. CCC 2015: 244-263 - [c2]Takuro Fukunaga, Shuichi Hirahara, Hiyori Yoshikawa:
Virtual machine placement for minimizing connection cost in data center networks. INFOCOM Workshops 2015: 486-491 - [i2]Shuichi Hirahara:
Identifying an Honest EXP^NP Oracle Among Many. CoRR abs/1502.07258 (2015) - [i1]Shuichi Hirahara, Osamu Watanabe:
Limits of Minimum Circuit Size Problem as Oracle. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c1]Shuichi Hirahara, Akitoshi Kawamura:
On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity. MFCS (2) 2014: 348-359
Coauthor Index
Igor C. Oliveira
aka: Igor Carboni Oliveira
aka: Igor Carboni Oliveira
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-18 20:27 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
