All reports by Author Shuichi Hirahara:

__
TR24-063
| 6th April 2024
__

Shuichi Hirahara, Mikito Nanashima#### One-Way Functions and Zero Knowledge

__
TR24-059
| 4th April 2024
__

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

__
TR24-058
| 29th March 2024
__

Shuichi Hirahara, Nobutaka Shimizu#### Planted Clique Conjectures Are Equivalent

__
TR24-039
| 20th February 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

__
TR24-023
| 21st January 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

__
TR23-171
| 15th November 2023
__

Shuichi Hirahara, Rahul Ilango, Ryan Williams#### Beating Brute Force for Compression Problems

__
TR23-144
| 22nd September 2023
__

Lijie Chen, Shuichi Hirahara, Hanlin Ren#### Symmetric Exponential Time Requires Near-Maximum Circuit Size

__
TR23-100
| 6th July 2023
__

Shuichi Hirahara, Mikito Nanashima#### Learning in Pessiland via Inductive Inference

__
TR23-070
| 9th May 2023
__

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren#### Bounded Relativization

__
TR23-037
| 28th March 2023
__

Shuichi Hirahara#### Capturing One-Way Functions via NP-Hardness of Meta-Complexity

__
TR23-035
| 22nd March 2023
__

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira#### A Duality Between One-Way Functions and Average-Case Symmetry of Information

__
TR23-026
| 15th March 2023
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification: Simplified, Optimized, and Unified

__
TR22-164
| 20th November 2022
__

Shuichi Hirahara, Mikito Nanashima#### Learning versus Pseudorandom Generators in Constant Parallel Time

__
TR22-127
| 12th September 2022
__

Eric Allender, Shuichi Hirahara, Harsha Tirumala#### Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Revisions: 2

__
TR22-119
| 24th August 2022
__

Shuichi Hirahara#### NP-Hardness of Learning Programs and Partial MCSP

__
TR22-108
| 18th July 2022
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification from Feasible Hard-Core Sets

__
TR21-166
| 21st November 2021
__

Lijie Chen, Shuichi Hirahara, Neekon Vafa#### Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

__
TR21-161
| 16th November 2021
__

Shuichi Hirahara, Mikito Nanashima#### On Worst-Case Learning in Relativized Heuristica

__
TR21-058
| 21st April 2021
__

Shuichi Hirahara#### Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

__
TR21-030
| 2nd March 2021
__

Shuichi Hirahara, Rahul Ilango, Bruno Loff#### Hardness of Constant-round Communication Complexity

__
TR21-010
| 11th February 2021
__

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle#### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

Revisions: 2

__
TR20-143
| 16th September 2020
__

Shuichi Hirahara#### Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

__
TR20-103
| 9th July 2020
__

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida#### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

__
TR20-050
| 18th April 2020
__

Shuichi Hirahara#### Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions

__
TR19-168
| 20th November 2019
__

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam#### Beyond Natural Proofs: Hardness Magnification and Locality

__
TR19-025
| 28th February 2019
__

Shuichi Hirahara, Osamu Watanabe#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

__
TR18-138
| 10th August 2018
__

Shuichi Hirahara#### Non-black-box Worst-case to Average-case Reductions within NP

Revisions: 1

__
TR18-030
| 9th February 2018
__

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam#### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

__
TR17-092
| 10th May 2017
__

Shuichi Hirahara#### A Duality Between Depth-Three Formulas and Approximation by Depth-Two

__
TR17-073
| 28th April 2017
__

Eric Allender, Shuichi Hirahara#### New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

__
TR15-198
| 30th November 2015
__

Shuichi Hirahara, Osamu Watanabe#### Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

Shuichi Hirahara, Mikito Nanashima

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of ... more >>>

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size $k \ll \sqrt{n}$ in an $n$-vertex Erd\H{o}s--R\'enyi random graph with a $k$-clique planted. In this paper, we prove the equivalence among many (in fact, \emph{most}) variants of planted clique conjectures, such as search ... more >>>

Shuichi Hirahara, Naoto Ohsaka

In the Minmax Set Cover Reconfiguration problem, given a set system $\mathcal{F}$ over a universe and its two covers $\mathcal{C}^\mathrm{start}$ and $\mathcal{C}^\mathrm{goal}$ of size $k$, we wish to transform $\mathcal{C}^\mathrm{start}$ into $\mathcal{C}^\mathrm{goal}$ by repeatedly adding or removing a single set of $\mathcal{F}$ while covering the universe in any intermediate state. ... more >>>

Shuichi Hirahara, Naoto Ohsaka

Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at ... more >>>

Shuichi Hirahara, Rahul Ilango, Ryan Williams

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>

Lijie Chen, Shuichi Hirahara, Hanlin Ren

We show that there is a language in $\mathrm{S}_2\mathrm{E}/_1$ (symmetric exponential time with one bit of advice) with circuit complexity at least $2^n/n$. In particular, the above also implies the same near-maximum circuit lower bounds for the classes $\Sigma_2\mathrm{E}$, $(\Sigma_2\mathrm{E}\cap\Pi_2\mathrm{E})/_1$, and $\mathrm{ZPE}^{\mathrm{NP}}/_1$. Previously, only "half-exponential" circuit lower bounds for these ... more >>>

Shuichi Hirahara, Mikito Nanashima

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.

In this paper, we develop a unified framework for constructing strong learning algorithms ... more >>>

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

Shuichi Hirahara

A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way ... more >>>

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>

Shuichi Hirahara, Mikito Nanashima

A polynomial-stretch pseudorandom generator (PPRG) in NC$^0$ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators ... more >>>

Eric Allender, Shuichi Hirahara, Harsha Tirumala

We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to ... more >>>

Shuichi Hirahara

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

Shuichi Hirahara, Nobutaka Shimizu

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>

Lijie Chen, Shuichi Hirahara, Neekon Vafa

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

Shuichi Hirahara, Mikito Nanashima

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption ... more >>>

Shuichi Hirahara

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this ... more >>>

Shuichi Hirahara, Rahul Ilango, Bruno Loff

How difficult is it to compute the communication complexity of a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard.

In this ... more >>>

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>>

Shuichi Hirahara

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:

DistPH is contained in ... more >>>

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Shuichi Hirahara

Hardness of computing the Kolmogorov complexity of a given string is closely tied to a security proof of hitting set generators, and thus understanding hardness of Kolmogorov complexity is one of the central questions in complexity theory. In this paper, we develop new proof techniques for showing hardness of computing ... more >>>

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

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

Shuichi Hirahara, Osamu Watanabe

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

Shuichi Hirahara

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... more >>>

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

Shuichi Hirahara

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>>

Eric Allender, Shuichi Hirahara

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Shuichi Hirahara, Osamu Watanabe

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>