Shuichi Hirahara

CoRR, August, 2025

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Complexity-Theoretic Inductive Inference.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Communication Complexity is NP-hard.

[BibT_eX]

[DOI]

Rahul Ilango

Bruno Loff

Electron. Colloquium Comput. Complex., 2025

Error-Correction of Matrix Multiplication Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

An Optimal Error-Correcting Reduction for Matrix Multiplication.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Asymptotic Inapproximability of Reconfiguration Problems: Maxmin k-Cut and Maxmin Ek-SAT.

[BibT_eX]

[DOI]

CoRR, 2024

One-Way Functions and pKt Complexity.

[BibT_eX]

[DOI]

Zhenjian Lu

Igor C. Oliveira

Proceedings of the Theory of Cryptography - 22nd International Conference, 2024

Planted Clique Conjectures Are Equivalent.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

One-Way Functions and Zero Knowledge.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Beating Brute Force for Compression Problems.

[BibT_eX]

[DOI]

Rahul Ilango

R. Ryan Williams

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Symmetric Exponential Time Requires Near-Maximum Circuit Size.

[BibT_eX]

[DOI]

Lijie Chen

Hanlin Ren

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications.

[BibT_eX]

[DOI]

Zhenjian Lu

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

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

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

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

[BibT_eX]

[DOI]

SIAM J. Comput., December, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Duality between One-Way Functions and Average-Case Symmetry of Information.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Regularization of Low Error PCPs and an Application to MCSP.

[BibT_eX]

[DOI]

Dana Moshkovitz

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

Learning Versus Pseudorandom Generators in Constant Parallel Time.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Kolmogorov Complexity Characterizes Statistical Zero Knowledge.

[BibT_eX]

[DOI]

Eric Allender

Harsha Tirumala

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Learning in Pessiland via Inductive Inference.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Bounded Relativization.

[BibT_eX]

[DOI]

Zhenjian Lu

Hanlin Ren

Proceedings of the 38th Computational Complexity Conference, 2023

2022

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

[BibT_eX]

[DOI]

Bull. EATCS, 2022

Excluding PH Pessiland.

[BibT_eX]

[DOI]

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

Errorless Versus Error-Prone Average-Case Complexity.

[BibT_eX]

[DOI]

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

Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions.

[BibT_eX]

[DOI]

Lijie Chen

Neekon Vafa

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

Hardness Self-Amplification from Feasible Hard-Core Sets.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

NP-Hardness of Learning Programs and Partial MCSP.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Finding Errorless Pessiland in Error-Prone Heuristica.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

Symmetry of Information from Meta-Complexity.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Average-case hardness of NP from exponential worst-case hardness assumptions.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

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

[BibT_eX]

[DOI]

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

Test of Quantumness with Small-Depth Quantum Circuits.

[BibT_eX]

[DOI]

François Le Gall

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

Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

On Worst-Case Learning in Relativized Heuristica.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Hardness of Constant-Round Communication Complexity.

[BibT_eX]

[DOI]

Rahul Ilango

Bruno Loff

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Unexpected hardness results for Kolmogorov complexity under uniform reductions.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

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

[BibT_eX]

[DOI]

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

Unexpected Power of Random Strings.

[BibT_eX]

[DOI]

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

Beyond Natural Proofs: Hardness Magnification and Locality.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

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

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

On Nonadaptive Security Reductions of Hitting Set Generators.

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the Approximation, 2020

2018

Non-Black-Box Worst-Case to Average-Case Reductions within NP.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.

[BibT_eX]

[DOI]

Igor C. Oliveira

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Eric Allender

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

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

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Limits of Minimum Circuit Size Problem as Oracle.

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

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

[BibT_eX]

[DOI]

Takuro Fukunaga

Hiyori Yoshikawa

Proceedings of the 2015 IEEE Conference on Computer Communications Workshops, 2015

Identifying an Honest EXP^NP Oracle Among Many.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity.

[BibT_eX]

[DOI]