Shuichi Hirahara

FOCS Conference 2025 Conference Paper

Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration

• Shuichi Hirahara
• Naoto Ohsaka

In the Maxmin Ek-SAT Reconfiguration problem, we are given a satisfiable k-CNF formula $\varphi$ where each clause contains exactly k literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\varphi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin Ek-SAT Reconfiguration is $1-\Theta\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-factor approximation algorithm for every $k \geqslant 3$. On the hardness side, we show that it is PSPACE-hard to approximate this problem within a factor of $1-\frac{1}{10 k}$ for every sufficiently large k. Note that an “NP analogue” of Maxmin Ek-SAT Reconfiguration is Max Ek-SAT, whose approximation threshold is $1-\frac{1}{2^{k}}$ shown by Håstad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its NP analogue. To prove the hardness result, we introduce a new “non-monotone” test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime.

STOC Conference 2025 Conference Paper

Error-Correction of Matrix Multiplication Algorithms

• Shuichi Hirahara
• Nobutaka Shimizu

Given an efficient algorithm that correctly computes a tiny fraction of the entries of the matrix multiplication of a small fraction of two matrices, can one design an efficient algorithm that computes matrix multiplication exactly for all the matrices? In this paper, we present such “worst-case exact to average-case approximate” reductions that transform any algorithm that correctly computes a tiny fraction of the entries of the multiplication of two uniformly random matrices over a finite field into a randomized worst-case algorithm that computes matrix multiplication for all the matrices. Under non-uniform reductions, we present an optimal reduction that error-corrects an algorithm whose output has expected Hamming distance 1 − 1/ p − ε to the multiplication of two random matrices over a finite field of size p for any positive constant ε > 0. Under uniform reductions, we present efficient reductions that correct a (1 − ε)-fraction of errors over a field of size p for all ε > 0 and for all sufficiently large p . We also present an optimal uniform reduction for the Online Matrix-Vector Multiplication problem. The non-uniform reduction is based on a new and simple proof of Yao’s XOR lemma for multi-output functions, whose complexity overhead is independent of the length of the output.

FOCS Conference 2025 Conference Paper

NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions

• Shuichi Hirahara
• Rahul Ilango

Whether the Minimum Circuit Size Problem (MCSP) is NP-hard or not is a long-standing open question. Indeed, Levin delayed the publication of his fundamental work on the theory of NP-completeness because he hoped to prove NP-completeness of MCSP. In this paper, we present the first plausible assumptions under which MCSP is NP-hard. Specifically, we prove that MCSP is NP-hard under deterministic quasi-polynomial-time nonadaptive reductions, assuming: •subexponentially-secure non-interactive witness indistinguishable proof systems for SAT exist, •coNP requires subexponential-size non-deterministic circuits, and•P NP /poly requires circuits of size Ω(2 n /n). This is arguably the first evidence that MCSP is not in coNP, which indicates that there is no short proof that witnesses the hardness of a function.

STOC Conference 2024 Conference Paper

Beating Brute Force for Compression Problems

• Shuichi Hirahara
• Rahul Ilango
• R. 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 ℓ · t ( n )), where ℓ is the length of the shortest description y and t ( n ) is the time complexity of f when it prints n -bit output. We prove that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size 2 4 ℓ / 5 · poly ( t ( n )), which is significantly more efficient for all ℓ ≫ log( t ( n )). Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length. As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s ( n ) on truth tables of size 2 n can be solved by circuits of size 2 4/5 · w + o ( w ) · poly (2 n ), where w = s ( n ) log 2 ( s ( n ) + n ). This improves over the brute-force approach of trying all possible size- s ( n ) circuits for all s ( n ) ≥ n . Similarly, the task of computing a short description of a string x when its t -complexity is at most ℓ, has circuits of size 2 4/5 ℓ · poly ( t ). We also give nontrivial circuits for computing Kt complexity on average, and for solving NP relations with “compressible” instance-witness pairs.

STOC Conference 2024 Conference Paper

One-Way Functions and Zero Knowledge

• 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 ( CZK ) proofs for all languages in NP . We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of zero knowledge. Specifically, we prove that the following are equivalent: - A one-way function exists. - NP ⊆ CZK and NP is hard in the worst case. - CZK is hard in the worst case and the problem GapMCSP of approximating circuit complexity is in CZK . The characterization above also holds for statistical and computational zero-knowledge argument systems. We further extend this characterization to a proof system with knowledge complexity O (log n ). In particular, we show that the existence of a one-way function is characterized by the worst-case hardness of CZK if GapMCSP has a proof system with knowledge complexity O (log n ). We complement this result by showing that NP admits an interactive proof system with knowledge complexity ω(log n ) under the existence of an exponentially hard auxiliary-input one-way function (which is a weaker primitive than an exponentially hard one-way function). We also characterize the existence of a robustly-often nonuniformly computable one-way function by the nondeterministic hardness of CZK under the weak assumption that PSPACE ⊈ AM . We present two applications of our results. First, we simplify the proof of the recent characterization of a one-way function by NP -hardness of a meta-computational problem and the worst-case hardness of NP given by Hirahara (STOC’23). Second, we show that if NP has a laconic zero-knowledge argument system, then there exists a public-key encryption scheme whose security can be based on the worst-case hardness of NP . This improves previous results which assume the existence of an indistinguishable obfuscation.

FOCS Conference 2024 Conference Paper

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

• Shuichi Hirahara
• Zhenjian Lu
• Mikito Nanashima

The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any samplable distribution admits a coding theorem for randomized time-bounded Kolmogorov complexity $(\text{rK}^{\text{poly}})$ is open and a common bottleneck in the recent literature of meta-complexity. Previous works bypassed this issue by considering probabilistic Kolmogorov complexity $(\text{pK}^{\text{poly}})$, in which public random bits are assumed to be available. In this paper, we present an efficient coding theorem for randomized Kolmogorov complexity under the non-existence of one-way functions, thereby removing the common bottleneck. This enables us to prove $\text{rK}^{\text{poly}}$ counterparts of virtually all the average-case results that were proved only for $\text{pK}^{\text{poly}}$, and enables the resolution of the following concrete open problems. 1)The existence of a one-way function is characterized by the failure of average-case symmetry of information for randomized time-bounded Kolmogorov complexity, as well as a conditional coding theorem for randomized time-bounded Kolmogorov complexity. This resolves the open problem of Hirahara, Ilango, Lu, Nanashima, and Oliveira (STOC'23). 2)Hirahara, Kabanets, Lu, and Oliveira (CCC'24) showed that randomized time-bounded Kolmogorov complexity admits search-to-decision reductions in the errorless average-case setting over any samplable distribution, and left open whether a similar result holds in the error-prone setting. We resolve this question affirmatively, and as a consequence, characterize the existence of a one-way function by the average-case hardness of computing $\text{rK}^{\text{poly}}$ with respect to an arbitrary samplable distribution, which is an $\text{rK}^{\text{poly}}$ analogue of the $\text{pK}^{\text{poly}}$ characterization of Liu and Pass (CRYPTO'23). The key technical lemma is that any distribution whose next bits are efficiently predictable admits an efficient encoding and decoding scheme, which could be of independent interest to data compression.

STOC Conference 2024 Conference Paper

Planted Clique Conjectures Are Equivalent

• Shuichi Hirahara
• Nobutaka Shimizu

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size k ≪ √ n in an n -vertex Erdős–Rényi random graph with a k -clique planted. In this paper, we prove the equivalence among many (in fact, most ) variants of planted clique conjectures, such as search versions with a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k -clique problem on incompressible graphs), decision versions with small and large success probabilities, and decision versions with adversarially chosen k and binomially distributed k . In particular, we establish the equivalence between the planted clique problem introduced by Jerrum and Kučera and its decision version suggested by Saks in the 1990s. Moreover, the equivalence among decision versions identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n -vertex random graph from a random graph with a k -clique planted with probability Θ( k 2 / n ) for any k ≤ √ n . We show that for any k , no polynomial-time algorithm can distinguish these two random graphs with probability ≫ k 2 / n if and only if the planted clique conjecture holds. The equivalence among search versions identifies the first one-way function that admits a polynomial-time security-preserving self-reduction from exponentially weak to strong one-way functions. These results reveal a detection-recovery gap in success probabilities for the planted clique problem. We also present another equivalence between the existence of a refutation algorithm for the planted clique problem and an average-case polynomial-time algorithm for the k -clique problem with respect to the Erdős–Rényi random graph.

STOC Conference 2024 Conference Paper

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

• Shuichi Hirahara
• Naoto Ohsaka

STOC Conference 2024 Conference Paper

Symmetric Exponential Time Requires Near-Maximum Circuit Size

• Lijie Chen 0001
• Shuichi Hirahara
• Hanlin Ren

We show that there is a language in S 2 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 Σ 2 E , (Σ 2 E ∩Π 2 E )/ 1 , and ZPE NP / 1 . Previously, only ”half-exponential” circuit lower bounds for these complexity classes were known, and the smallest complexity class known to require exponential circuit complexity was Δ 3 E = E Σ 2 P (Miltersen, Vinodchandran, and Watanabe COCOON’99). Our circuit lower bounds are corollaries of an unconditional zero-error pseudodeterministic algorithm with an NP oracle and one bit of advice ( FZPP NP / 1 ) that solves the range avoidance problem infinitely often. This algorithm also implies unconditional infinitely-often pseudodeterministic FZPP NP / 1 constructions for Ramsey graphs, rigid matrices, two-source extractors, linear codes, and K poly -random strings with nearly optimal parameters. Our proofs relativize. The two main technical ingredients are (1) Korten’s P NP reduction from the range avoidance problem to constructing hard truth tables (FOCS’21), which was in turn inspired by a result of Jeřábek on provability in Bounded Arithmetic (Ann. Pure Appl. Log. 2004); and (2) the recent iterative win-win paradigm of Chen, Lu, Oliveira, Ren, and Santhanam (FOCS’23).

STOC Conference 2023 Conference Paper

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

• Shuichi Hirahara
• Rahul Ilango
• Zhenjian Lu
• Mikito Nanashima
• Igor C. Oliveira 0001

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) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.

STOC Conference 2023 Conference Paper

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

• 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 function. Specifically, we generalize the notion of time-bounded conditional Kolmogorov complexity to *distributional Kolmogorov complexity*, and prove that a one-way function exists if and only if it is NP-hard to approximate the distributional Kolmogorov complexity under randomized polynomial-time reductions and NP is hard in the worst case. We also propose the *Meta-Complexity Padding Conjecture*, which postulates that distributional Kolmogorov complexity is paddable by an approximation-preserving reduction. Under this conjecture, we prove that the worst-case hardness of an approximate version of the Minimum Circuit Size Problem characterizes the existence of a one-way function.

TCS Journal 2023 Journal Article

Cryptographic hardness under projections for time-bounded Kolmogorov complexity

• 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 complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP -Turing reductions; neither is known to be NP -complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P ) under nonuniform ≤ m NC 0 reductions. In this paper, we improve this, to show that MKTP ‾ is hard for the (apparently larger) class NISZK L under not only ≤ m NC 0 reductions but even under projections. Also MKTP ‾ is hard for NISZK under ≤ m P / poly reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK L is the non-interactive version of the class SZK L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP ).

STOC Conference 2023 Conference Paper

Hardness Self-Amplification: Simplified, Optimized, and Unified

• 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 hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdős–Rényi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.

FOCS Conference 2023 Conference Paper

Learning in Pessiland via Inductive Inference

• 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 under the nonexistence of a one-way function, indicating a positive aspect of Pessiland. Using our framework, we improve the learning algorithm for adaptively changing distributions, which was introduced by Naor and Rothblum (ICML’06). Although the previous learner assumes the knowledge of underlying distributions, our learner is universal, i. e. , does not assume any knowledge on distributions, and has better sample complexity. We also employ our framework to construct a strong agnostic learner with optimal sample complexity, which improves the previous PAC learner of Blum, Furst, Kearns, and Lipton (Crypto’93). Our learning algorithms are worst-case algorithms that run in exponential time with respect to computational depth, and as a by-product, we present the first characterization of the existence of a one-way function by the worst-case hardness of some promise problem in AM. As a corollary of our results, we establish the robustness of average-case learning, that is, the equivalence among various average-case learning tasks, such as (strong and weak) agnostic learning, learning adaptively changing distributions with respect to arbitrary unknown distributions, and weak learning with membership queries with respect to the uniform distribution. Our framework is based on the theory of Solomonoff’s inductive inference and the universal extrapolation algorithm of Impagliazzo and Levin (FOCS’90). Conceptually, the framework demonstrates that Pessiland is, in fact, a wonderland for machine learning in which various learning tasks can be efficiently solved by the generic algorithm of universal extrapolation.

FOCS Conference 2022 Conference Paper

Hardness Self-Amplification from Feasible Hard-Core Sets

• Shuichi Hirahara
• Nobutaka Shimizu

We consider the question of hardness self-amplification: Given a Boolean function f that is hard to compute on an o (1)-fraction of inputs drawn from some distribution, can we prove that f is hard to compute on a $(\displaystyle \frac{1}{2}-o(1))$-fraction of inputs drawn from the same distribution? We prove hardness self-amplification results for natural distributional problems studied in fine-grained average-case complexity, such as the problem of counting the number of the triangles modulo 2 in a random tripartite graph and the online vector-matrix-vector multiplication problem over $\mathbb{F}_{2}$. More generally, we show that any problem that can be decomposed into "computationally disjoint" subsets of inputs admits hardness self-amplification. This is proved by generalizing the security proof of the NisanWigderson pseudorandom generator, in which case nearly disjoint subsets of inputs are considered. At the core of our proof techniques is a new notion of feasible hard-core set, which generalizes Impagliazzo’s hard-core set [Impagliazzo, FOCS’95]. We show that any weak average-case hard function f has a feasible hard-core set H: any small H-oracle circuit (that is allowed to make queries q to H if $f(q)$ can be computed without the oracle) fails to compute f on a $(\displaystyle \frac{1}{2}-o(1))$-fraction of inputs in H.

FOCS Conference 2022 Conference Paper

NP-Hardness of Learning Programs and Partial MCSP

• 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 of learning programs. In this paper, we overcome Ko’s relativization barrier and prove NP-hardness of learning programs under randomized polynomial-time many-one reductions. Our result is provably non-relativizing, and comes somewhat close to the parameter range of improper learning: We observe that mildly improving our inapproximability factor is sufficient to exclude Heuristica, i. e. , show the equivalence between average-case and worst-case complexities of N P. We also make progress on another long-standing open question of showing NP-hardness of the Minimum Circuit Size Problem (MCSP). We prove NP-hardness of the partial function variant of MCSP as well as other meta-computational problems, such as the problems MKTP * and MINKT * of computing the time-bounded Kolmogorov complexity of a given partial string, under randomized polynomial-time reductions. Our proofs are algorithmic information (a. k. a. Kolmogorov complexity) theoretic. We utilize black-box pseudorandom generator constructions, such as the Nisan-Wigderson generator, as a one-time encryption scheme secure against a program which “does not know” a random function. Our key technical contribution is to quantify the “knowledge” of a program by using conditional Kolmogorov complexity and show that no small program can know many random functions.

STOC Conference 2021 Conference Paper

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

• 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 question has been discussed from various perspectives based on technical barrier results, such as the limits of black-box reductions and the non-existence of worst-case hardness amplification procedures in PH. In this paper, we overcome these barriers and resolve the open question by presenting the following main results: 1. UP ⊈ DTIME (2 O ( n / log n ) ) implies DistNP ⊈ AvgP . 2. PH ⊈ DTIME (2 O ( n / log n ) ) implies DistPH ⊈ AvgP . 3. NP ⊈ DTIME (2 O ( n / log n ) ) implies DistNP ⊈ Avg P P . Here, Avg P P denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worst-case polynomial-time. We complement this result by showing that DistPH ⊈ AvgP if and only if DistPH ⊈ Avg P P . At the core of all of our results is a new notion of universal heuristic scheme, whose running time is P-computable average-case polynomial time under every polynomial-time samplable distribution. Our proofs are based on the meta-complexity of time-bounded Kolmogorov complexity: We analyze average-case complexity through the lens of worst-case meta-complexity using a new “algorithmic” proof of language compression and weak symmetry of information for time-bounded Kolmogorov complexity.

SODA Conference 2021 Conference Paper

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

• Shuichi Hirahara
• Nobutaka Shimizu

In this paper, we seek a natural problem and a natural distribution of instances such that any O ( n c – ∊ ) time algorithm fails to solve most instances drawn from the distribution, while the problem admits an n c + o (1) -time algorithm that correctly solves all instances. Specifically, we consider the K a, b counting problem in a random bipartite graph, where K a, b is a complete bipartite graph and a and b are constants. Our distribution consists of the binomial random bipartite graphs B αn, βn with edge density 1/2, where α and β are drawn uniformly at random from {1, …, a } and {1, …, b }, respectively. We determine the nearly optimal average-case complexity of this counting problem by proving the following results. Conditional Tight Worst-Case Complexity. Under the Strong Exponential Time Hypothesis, for any constants a ≥ 3 and ∊ > 0, there exists a constant b = b ( a, ∊ ) such that no O ( n a – ∊ )-time algorithm counts the number of K a, b subgraphs in a given n -vertex graph. On the other hand, for any constant a ≥ 8 and any b = b ( n ), we can count all K a, b subgraphs in time bn a + o (1). Worst-to-Average Reduction. If there exists a T(n) -time randomized heuristic algorithm that solves the K a, b subgraph counting problem on a random graph B αn, βn with success probability 1 — 1/polylog( n ), then there exists a T ( n )polylog( n )-time randomized algorithm that solves the K a, b subgraph counting problem for any input with success probability 2/3. Fine-Grained Hardness Amplification. Suppose that there is a T ( n )-time algorithm with success probability n – ∊ that computes the parity of the number of K a, b subgraphs in H, where is the disjoint union of k = O (∊ log n ) i. i. d. random graphs G 1, …, G k each of which is drawn from the distribution of B αn, βn. Then there is a T ( n ) n O (∊) -time randomized algorithm that counts K a, b subgraphs for any input with success probability 2/3. The central idea behind these results is colorful subgraphs. For the first result, we reduce the k -Orthogonal Vectors problem to the colorful K a, b detection problem. In the second result, we establish a worst-case-to-average-case reduction for a colorful subgraph counting problem based on the binary-extension technique given by [Boix-Adserà, Brennan, and Bresler; FOCS19]. Then, we reduce colorful K a, b counting to K a, b counting. Regarding the third result, we prove the classical XOR lemma and the direct product theorem in the fine-grained setting for subgraph counting problems. The core of the proof is an O (log n )-round doubly-efficient interactive proof system for the colorful subgraph counting problem such that the honest prover is asked to solve polylog( n ) instances of the counting problem. The new protocol improves the known interactive proof system for the t -clique counting problem given by [Goldreich and Rothblum; FOCS18] in terms of query complexity.

FOCS Conference 2021 Conference Paper

On Worst-Case Learning in Relativized Heuristica

• 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 might be sufficient for worst-case learning than the feasibility of worst-case algorithms for NP problems. In this study, we investigate whether these worst-case re-quirements for learning are satisfied on the basis of only average-case assumptions in order to understand the nature of learning. First, we construct a strong worst-case learner based on the assumption that DistNP ⊆ AvgP, i. e. , in Heuristica. Our learner agnostically learns all polynomial-size circuits on all unknown P/ poly-samplable distributions in polynomial time, where the complexity of learning depends on the complexity of sampling examples. Second, we study the limitation of relativizing constructions of learners based on average-case heuristic algorithms. Specifically, we construct a powerful oracle such that DistPH ⊆ AvgP, i. e. , every problem in PH is easy on average, whereas UP ∩ coUP and PAC learning on almost-uniform distributions are hard even for 2 n/w(1og n) - time algorithms in the relativized world, which improves the oracle separation presented by Impagliazzo (CCC 2011). The core concept of our improvements is the consideration of a switching lemma on a large alphabet, which may be of independent interest. The lower bound on the time complexity is nearly optimal because Hirahara (STOC 2021) showed that DistPH ⊆ AvgP implies that PH can be solved in time 2 O(n/ log n) under any relativized world. The full version of this paper is available on ECCC [1].

MFCS Conference 2021 Conference Paper

Test of Quantumness with Small-Depth Quantum Circuits

• Shuichi Hirahara
• François Le Gall

Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a test that can be solved efficiently by a quantum computer but cannot be solved by a classical polynomial-time computer under the LWE assumption. This test has lead to several cryptographic applications. In particular, it has been applied to producing certifiable randomness from a single untrusted quantum device, self-testing a single quantum device and device-independent quantum key distribution. In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits: constant-depth quantum circuits combined with logarithmic-depth classical computation. This reveals novel complexity-theoretic properties of this fundamental test of quantumness and gives new concrete evidence of the superiority of small-depth quantum circuits over classical computation.

FOCS Conference 2020 Conference Paper

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

• 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 ⊆ AvgP ( i. e. , PH is easy on average) ⇐⇒ GapMINKT PH ∈ P. In fact, our equivalence is significantly broad: A number of statements on several fundamental notions of complexity theory, such as errorless and one-sided-error average-case complexity, sublinear-time-bounded and polynomial-time-bounded Kolmogorov complexity, and PH-computable hitting set generators, are all shown to be equivalent. Our equivalence provides fundamentally new proof techniques for analyzing average-case complexity through the lens of meta-complexity of time-bounded Kolmogorov complexity and resolves, as immediate corollaries, questions of equivalence among different notions of average-case complexity of PH: low success versus high success probabilities (i. e. , a hardness amplification theorem for DistPH against uniform algorithms) and errorless versus one-sided-error average-case complexity of PH. Our results are based on a sequence of new technical results that further develops the proof techniques of the author's previous work on the non-black-box worst-case to average-case reduction and unexpected hardness results for Kolmogorov complexity (FOCS'18, CCC'20, ITCS'20, STOC'20). Among other things, we prove the following. 1) GapMINKT NP ∈ P implies P = BPP. At the core of the proof is a new black-box hitting set generator construction whose reconstruction algorithm uses few random bits, which also improves the approximation quality of the nonblack-box worst-case to average-case reduction without using a pseudorandom generator. 2) GapMINKT PH ∈ P implies DistPH ⊆ AvgBPP = AvgP. 3) If MINKT PH ∈ P is easy on a 1/poly(n)-fraction of inputs, then GapMINKT PH ∈ P. This improves the error tolerance of the previous non-black-box worst-case to average-case reduction. The full version of the paper is available on ECCC.

NeurIPS Conference 2020 Conference Paper

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

• Shinji Ito
• Shuichi Hirahara
• Tasuku Soma
• Yuichi Yoshida

We propose novel algorithms with first- and second-order regret bounds for adversarial linear bandits. These regret bounds imply that our algorithms perform well when there is an action achieving a small cumulative loss or the loss has a small variance. In addition, we need only assumptions weaker than those of existing algorithms; our algorithms work on discrete action sets as well as continuous ones without a priori knowledge about losses, and they run efficiently if a linear optimization oracle for the action set is available. These results are obtained by combining optimistic online optimization, continuous multiplicative weight update methods, and a novel technique that we refer to as distribution truncation. We also show that the regret bounds of our algorithms are tight up to polylogarithmic factors.

STOC Conference 2020 Conference Paper

Unexpected hardness results for Kolmogorov complexity under uniform reductions

• Shuichi Hirahara

FOCS Conference 2018 Conference Paper

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

• 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 averagecase reductions are not likely to be used for reducing any worstcase problem outside coNP to a distributional NP problem. This paper overcomes the barrier. We present the first nonblack-box worst-case to average-case reduction from a problem outside coNP (unless Random 3SAT is easy for coNP algorithms) to a distributional NP problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT), and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time bounded Kolmogorov complexity k within an additive error ̅O(√ k) if its average-case version admits an errorless heuris tic polynomial-time algorithm. (The converse direction also holds under a plausible derandomization assumption.) We also show that, given a truth table of size 2 n approximating the minimum circuit size within a factor of 2( 1-ε jn is in BPP for some constant € > 0 if and only if its average-case version is easy. Based on our results, we propose a research program for excluding Heuristica, i. e. , establishing an equivalence between the worst-case and average-case hardness of NP through the lens of MINKT or the Minimum Circuit Size Problem (MCSP).

MFCS Conference 2017 Conference Paper

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

• 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) within a factor of n^{1 - o(1)} is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. We also prove that MKTP is hard for the complexity class DET under non-uniform NC^0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of "local" reductions such as NC^0 reductions. We exploit this local reduction to obtain several new consequences: * MKTP is not in AC^0[p]. * Circuit size lower bounds are equivalent to hardness of a relativized version MKTP^A of MKTP under a class of uniform AC^0 reductions, for a large class of sets A. * Hardness of MCSP^A implies hardness of MKTP^A for a wide class of sets A. This is the first result directly relating the complexity of MCSP^A and MKTP^A, for any A.