The Gap Between Average-Case and Worst-Case Complexity

Halley Goldberg; Igor C. Oliveira; Jingyi Lyu; Jinqiao Hu; Zhenjian Lu

REVIEW

The Gap Between Average-Case and Worst-Case Complexity

Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira

Computational Complexity · Submitted 13 Oct 2026 · 35 references

Pith's verdict: Equivalence between average-case vs worst-case for PH and a meta-complexity gap reduction – a conceptual advance built heavily on [HLO26].

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 15, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2610.19162 (version 1)

Pith IDF5HW3VLI, Pith's permanent record of this paper and its review

CitationHalley Goldberg, Igor C. Oliveira, Jingyi Lyu, Jinqiao Hu, Zhenjian Lu. "The Gap Between Average-Case and Worst-Case Complexity." arXiv:2610.19162 (2026). https://pith.science/paper/F5HW3VLI

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper proves that excluding PH Heuristica (DistPH⊆AvgBPP ⇒ PH⊆BPP) is equivalent to a gap reduction for MINpKT with PH oracle: standard-gap easiness implying mild-gap easiness. This is a clean conceptual reframing that pins down why meta-complexity seems unavoidable for this problem. The result is genuine and not circular – it synthesizes techniques from Hirahara [Hir20] and Hu-Lu-Oliveira [HLO26] into an equivalence that was not previously stated. The additional results on average-case gap elimination and a relativization barrier are solid and add value.

The main soft spot is in the hard direction of the equivalence (Lemma 3.4 / Claim 3.10). The reconstruction lemma (Lemma 2.15) is stated for unconditional Kolmogorov complexity, but the argument needs a bound on pK^{poly(t)}(y|x), i.e., conditional on x. The paper applies the unconditional lemma with a distinguisher that depends on x and asserts the conditional bound without providing a conditional variant or a justification for how the auxiliary input is absorbed. This step is currently not fully justified and would need to be checked carefully. The rest of the proof is well-structured and relies on prior work transparently.

Overall, the main equivalence is a significant conceptual contribution, and the paper is honestly written about its reliance on [HLO26]. I would send it to a referee with a note to examine the reconstruction step. The paper deserves a serious review because the implications for the average-case vs worst-case question are important, and even if the proof has a fixable gap, the framing itself is valuable.

I would bring it to our reading group. I might cite it if I work on average-case complexity, but it is more of a foundation for others to build on.

Referee report

Major objections (3)

[§3.1.2, Claim 3.10] The argument that a distinguisher A (with x fixed) for D1=(x,DP_k(y,U^{mk})) vs D2=(x,U^{mk+k}) yields a bound on conditional complexity pK^{p_2(t)}(y|x) ≤ k+O(log t) invokes Lemma 2.15, which provides an unconditional bound pK^{poly(...)}(seed) ≤ k+O(log t) for the seed of the direct product generator. In Claim 3.10 the seed is y, but the distinguisher takes x as part of its input; the reconstruction lemma as stated does not account for auxiliary input x. The paper does not provide a conditional variant or cite one from prior work. Without this adaptation, the claimed lower bound on ℓ-pK_{b/n^3, d/n^3}^{t,SAT}(x,y) does not follow, so the entire oracle removal inequality supporting Lemma 3.4 is unsupported.
[§3.1.2, Lemma 3.4 (proof sketch)] The proof of Lemma 3.4 is given as a sketch that defers to [HLO26] for several key lemmas (Lemma 3.7, Lemma 3.8, and the telescoping argument). While deferred proofs are permissible, the paper must ensure that the adaptation from the non-gap setting of [HLO26] to the mild-gap setting is fully verified. The telescoping argument relies on the additive time overhead property of ℓ-pK; the paper should confirm that the lemmas from [HLO26] relativize to SAT oracle and to the mild-gap parameters exactly as needed.
[§3.3.1, Claim 3.19] The algorithm Approx-depth is defined using two invocations of an approximation algorithm for pK^{t,O} whose existence follows from Gap-MINpKT^PH ∈ prBPP. However, the output s is required to satisfy a specific lower bound (involving pK^{t,O}(x)-pK^{p(t),O}(x)) and an upper bound (involving pK^{ρ^{-1}(t),O}(x)-pK^{ρ(p(t)),O}(x)). The derivation of these bounds from the approximation guarantees needs to account for the fact that the approximation algorithm operates with a gap parameter ρ and may have additive slack. The claim should be stated with explicit error margins and verified that the composition of two invocations yields the claimed inequality for all x with high probability.

Minor objections (5)

[§1.2, Figure 1] The caption and the figure describe NO_poly(t) ⊆ NO_{t+poly(n)}. The notation would be clearer if the time bounds t, poly(t), t+poly(n) were explicitly marked on the diagram axes.
[§2.2, Definition 2.1] The definition of K^{t,O}(x|y;r) requires the program to output x within t steps. It should be specified whether the time bound t counts steps of the universal machine or steps of the described machine. The text later assumes a time-efficient universal machine; clarifying this earlier would help.
[§3.1.2, Equation (8)] The notation pK^{t,SAT}(x) is used before it is formally introduced for the SAT oracle (the paper defines pK^{t,O} with general O but often uses SAT as O). Consider defining pK^{t,SAT} explicitly in the preliminaries.
[§5.2, proof of Claim 5.6] Equation (23) uses a success probability bound of 1-1/α(n)^2 obtained by standard error reduction. The derivation should note that α is a polynomial to be chosen later, and that the error reduction requires that the underlying heuristic algorithm works for all sufficiently large n, which is implicit in the definition of HeurBPP.
[References] Reference [HLO26] is to appear at CCC 2026. Since the paper relies heavily on [HLO26] (Lemmas 3.7, 3.8, the ℓ-pK framework), the authors should confirm that the published version is available and that the needed lemmas are established in the form used here.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Excluding PH Heuristica is equivalent to a meta-complexity gap reduction.

The reading

The paper establishes that the long-standing question of whether average-case easiness of the polynomial hierarchy (PH) implies its worst-case easiness—the exclusion of PH Heuristica—is exactly equivalent to a purely meta-computational problem: whether efficient algorithms for the standard gap version of the time-bounded Kolmogorov complexity problem MINpKT with PH oracle imply efficient algorithms for a mild gap version. This equivalence, proved via two correspondences linking average-case and worst-case complexity to meta-complexity, shows that meta-complexity is not merely a tool but is inherent to the problem. The paper further proves that in the average-case setting the gap can be eliminated entirely, and that any worst-case gap reduction must use nonrelativizing techniques, establishing a relativization barrier.

What carries the argument

The central objects are the promise problems Gap-MINpKT^PH, where a YES instance has small time-bounded Kolmogorov complexity at time t and a NO instance has large complexity at time poly(t), and Mild-Gap-MINpKT^PH, where the NO threshold uses time t+poly(n) instead. The proof employs time-bounded probabilistic Kolmogorov complexity pK^t with PH oracle, symmetry of information, language compression for nondeterministic Kolmogorov complexity, and a lifted measure ℓ-pK that allows additive time increases, enabling a telescoping argument to eliminate the computational depth term.

Extended reading notes

Core claim

The central claim is that the implication DistPH⊆AvgBPP ⇒ PH⊆BPP is equivalent to the implication Gap-MINpKT^PH ∈ prBPP ⇒ Mild-Gap-MINpKT^PH ∈ prBPP. This is proved by two separate equivalences: DistPH⊆AvgBPP ⇔ Gap-MINpKT^PH ∈ prBPP, and PH⊆BPP ⇔ Mild-Gap-MINpKT^PH ∈ prBPP. Thus, the average-case versus worst-case complexity of PH reduces entirely to a comparison between two approximation regimes for probabilistic time-bounded Kolmogorov complexity with PH oracle access.

Load-bearing premise

The proof of the hard direction (Lemma 3.4) relies on the language compression property for pK^t,SAT from [HLO26] and on the assumption that the mild-gap version of MINpKT^SAT is easy, which together allow an oracle removal inequality via ℓ-pK and telescoping; several key lemmas are deferred to [HLO26] and their correctness in the relativized mild-gap setting is assumed.

Editorial extensions

If this is right

Any proof that DistPH⊆AvgBPP implies PH⊆BPP must implicitly establish the gap reduction for MINpKT^PH, showing meta-complexity is unavoidable.
The average-case gap reduction (Theorem 1.2) shows that for both zero-error and two-sided error settings, the distinction between gap and no-gap versions of MINpKT^PH vanishes on average.
The relativization barrier implies that nonrelativizing techniques are necessary for the worst-case gap reduction, aligning with known barriers in complexity theory.
The equivalence suggests that the complexity of MINpKT with PH oracle is a central question for understanding the average-case complexity of the polynomial hierarchy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The equivalence implies that a polynomial-time algorithm for Gap-MINpKT^PH would directly resolve the PH Heuristica problem, making meta-complexity a concrete pathway to this fundamental question.
The mild-gap problem captures the worst-case complexity of PH almost exactly, so its hardness is tied to the existence of efficient algorithms for all of PH.
The average-case gap elimination suggests that the core difficulty lies in the worst-case setting, where the time gap between YES and NO instances is significant and requires nonrelativizing reasoning.

Original abstract

Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-15: 1 request, 7,892 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.48 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.62 · compares with prior results 0.89 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography.	background 1.00	0.03	0.02	asserted 1.00
s1	A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$).	background 0.94	0.05	0.02	asserted 0.99
s2	In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$.	background 0.99	0.02	0.06	asserted 1.00
s3	Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way.	background 0.55	0.15	0.05	asserted 0.96
s4	We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence.	contribution 0.47	0.44	0.15	asserted 1.00
s5	Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version.	result 0.76	0.95	0.71	asserted 1.00
s6	Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$.	method 0.24	0.36	0.07	asserted 1.00
s7	Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity.	interpretation 0.88	0.38	0.21	hedged possibility 0.99
s8	We make progress by proving that the gap in running time can be eliminated in the average-case setting.	result 0.87	0.95	0.13	asserted 1.00
s9	Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.	result 0.97	0.93	0.18	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Instance sets for the standard and mild gap problems for fixed description length bound s and time bound t. Under poly(t) ≥ t+poly(n), monotonicity of time-bounded probabilistic Kolmogorov complexity gives pKt+poly(n),O(x) ≥ pKpoly(t),O(x). Consequently, NOpoly(t) ⊆ NOt+poly(n) . For an oracle-dependent problem A such as Gap-MINpKT or Mild-Gap-MINpKT, the notation APH ∈ prBPP means that the corresponding promise problem is in randomized polynomial time for every oracle language O ∈ PH. Theorem 1.1 (Main Equivalence). The following statements are equivalent: 1. (Exclusion of PH…

**Figure 2.** Relating the average-case and worst-case complexities of the polynomial hierarchy (

Figures reproduced from arXiv:2610.19162 by the authors.

References

Works cited (35)

[1]

Andrej Bogdanov and Luca Trevisan , title =. Foundations and Trends in Theoretical Computer Science , volume =

View on Pith
[2]

Leonid A. Levin , title =. SIAM Journal on Computing , volume =. 1986 , doi =

View on Pith 1986
[3]

Joan Feigenbaum and Lance Fortnow , title =. SIAM Journal on Computing , volume =. 1993 , doi =

View on Pith 1993
[4]

Russell Impagliazzo , title =. Proceedings of the Tenth Annual Structure in Complexity Theory Conference , pages =

View on Pith
[5]

Andrej Bogdanov and Luca Trevisan , title =. Symposium on Foundations of Computer Science , pages =

View on Pith
[6]

Shuichi Hirahara , title =. Symposium on Theory of Computing , pages =

View on Pith
[7]

Halley Goldberg and Valentine Kabanets and Zhenjian Lu and Igor C. Oliveira , title =. Computational Complexity Conference , pages =

View on Pith
[8]

Halley Goldberg and Valentine Kabanets , title =. Electron. Colloquium Comput. Complex. , volume =. 2022 , url =

View on Pith 2022
[9]

Shuichi Hirahara , title =. Symposium on Foundations of Computer Science , pages =

View on Pith
[10]

Shuichi Hirahara , title =. Bull. EATCS , volume =. 2022 , url =

View on Pith 2022
[11]

Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma , title =. Computational Complexity , volume =

View on Pith
[12]

Lijie Chen and Shuichi Hirahara and Neekon Vafa , title =. Innovations in Theoretical Computer Science Conference , pages =. 2022 , doi =

View on Pith 2022
[13]

Shuichi Hirahara , title =. Computational Complexity Conference , pages =. 2022 , doi =

View on Pith 2022
[14]

Russell Impagliazzo and Leonid A. Levin , title =. Symposium on Foundations of Computer Science , pages =

View on Pith
[15]

Jinqiao Hu and Zhenjian Lu and Igor C. Oliveira , journal =. Computational Complexity Conference , title =

View on Pith
[16]

Halley Goldberg and Jinqiao Hu and Zhenjian Lu and Jingyi Lyu and Igor C. Oliveira , title =. Electron. Colloquium Comput. Complex. , volume =. 2025 , url =

View on Pith 2025
[17]

Shuichi Hirahara and Valentine Kabanets and Zhenjian Lu and Igor C. Oliveira , title =. Computational Complexity Conference , pages =

View on Pith
[18]

Rahul Ilango , title =. Symposium on Foundations of Computer Science , pages =

View on Pith
[19]

Yanyi Liu and Rafael Pass , title =. Innovations in Theoretical Computer Science , year =

View on Pith
[20]

Hanlin Ren and Rahul Santhanam , title =. International Symposium on Theoretical Aspects of Computer Science , pages =. 2022 , doi =

View on Pith 2022
[21]

Shuichi Hirahara and Zhenjian Lu and Hanlin Ren , title =. Computational Complexity Conference , pages =. 2023 , doi =

View on Pith 2023
[22]

Zhenjian Lu and Igor C. Oliveira and Marius Zimand , title =. International Colloquium on Automata, Languages, and Programming , pages =

View on Pith
[23]

Ming Li and Paul M. B. Vitanyi , title =

View on Pith
[24]

Madhu Sudan , title =. J. Complex. , volume =. 1997 , url =. doi:10.1006/JCOM.1997.0439 , timestamp =

View on Pith doi:10.1006/jcom.1997.0439 1997
[25]

Russell Impagliazzo and Avi Wigderson , title =. Symposium on Theory of Computing , pages =

View on Pith
[26]

Raz, Ran and Reingold, Omer and Vadhan, Salil P. , title =. J. Comput. Syst. Sci. , volume =. 2002 , doi =

View on Pith 2002
[27]

Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira , title =. Symposium on Theory of Computing , pages =

View on Pith
[28]

Russell Impagliazzo , title =. Conference on Computational Complexity , pages =

View on Pith
[29]

Shuichi Hirahara and Mikito Nanashima , title =. Symposium on Foundations of Computer Science , pages =

View on Pith
[30]

Rahul Ilango and Hanlin Ren and Rahul Santhanam , title =. Symposium on Theory of Computing , pages =

View on Pith
[31]

Yanyi Liu and Rafael Pass , title =. Annual Cryptology Conference , pages =. 2023 , timestamp =. doi:10.1007/978-3-031-38545-2_21 , _bib2doi_selected =

View on Pith doi:10.1007/978-3-031-38545-2_21 2023
[32]

Johan H. A Pseudorandom Generator from any One-way Function , journal =

View on Pith
[33]

Shuichi Hirahara and Rahul Santhanam , title =. Innovations in Theoretical Computer Science Conference , pages =. 2022 , url =. doi:10.4230/LIPICS.ITCS.2022.85 , timestamp =

View on Pith doi:10.4230/lipics.itcs.2022.85 2022
[34]

Meta-. Spring 2023 , url =

View on Pith 2023
[35]

Zhenjian Lu and Igor C. Oliveira , title =. Bull. 2022 , url =

View on Pith 2022

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Andrej Bogdanov and Luca Trevisan , title =. Foundations and Trends in Theoretical Computer Science , volume =

View on Pith

[2] [2]

Leonid A. Levin , title =. SIAM Journal on Computing , volume =. 1986 , doi =

View on Pith 1986

[3] [3]

Joan Feigenbaum and Lance Fortnow , title =. SIAM Journal on Computing , volume =. 1993 , doi =

View on Pith 1993

[4] [4]

Russell Impagliazzo , title =. Proceedings of the Tenth Annual Structure in Complexity Theory Conference , pages =

View on Pith

[5] [5]

Andrej Bogdanov and Luca Trevisan , title =. Symposium on Foundations of Computer Science , pages =

View on Pith

[6] [6]

Shuichi Hirahara , title =. Symposium on Theory of Computing , pages =

View on Pith

[7] [7]

Halley Goldberg and Valentine Kabanets and Zhenjian Lu and Igor C. Oliveira , title =. Computational Complexity Conference , pages =

View on Pith

[8] [8]

Halley Goldberg and Valentine Kabanets , title =. Electron. Colloquium Comput. Complex. , volume =. 2022 , url =

View on Pith 2022

[9] [9]

Shuichi Hirahara , title =. Symposium on Foundations of Computer Science , pages =

View on Pith

[10] [10]

Shuichi Hirahara , title =. Bull. EATCS , volume =. 2022 , url =

View on Pith 2022

[11] [11]

Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma , title =. Computational Complexity , volume =

View on Pith

[12] [12]

Lijie Chen and Shuichi Hirahara and Neekon Vafa , title =. Innovations in Theoretical Computer Science Conference , pages =. 2022 , doi =

View on Pith 2022

[13] [13]

Shuichi Hirahara , title =. Computational Complexity Conference , pages =. 2022 , doi =

View on Pith 2022

[14] [14]

Russell Impagliazzo and Leonid A. Levin , title =. Symposium on Foundations of Computer Science , pages =

View on Pith

[15] [15]

Jinqiao Hu and Zhenjian Lu and Igor C. Oliveira , journal =. Computational Complexity Conference , title =

View on Pith

[16] [16]

Halley Goldberg and Jinqiao Hu and Zhenjian Lu and Jingyi Lyu and Igor C. Oliveira , title =. Electron. Colloquium Comput. Complex. , volume =. 2025 , url =

View on Pith 2025

[17] [17]

Shuichi Hirahara and Valentine Kabanets and Zhenjian Lu and Igor C. Oliveira , title =. Computational Complexity Conference , pages =

View on Pith

[18] [18]

Rahul Ilango , title =. Symposium on Foundations of Computer Science , pages =

View on Pith

[19] [19]

Yanyi Liu and Rafael Pass , title =. Innovations in Theoretical Computer Science , year =

View on Pith

[20] [20]

Hanlin Ren and Rahul Santhanam , title =. International Symposium on Theoretical Aspects of Computer Science , pages =. 2022 , doi =

View on Pith 2022

[21] [21]

Shuichi Hirahara and Zhenjian Lu and Hanlin Ren , title =. Computational Complexity Conference , pages =. 2023 , doi =

View on Pith 2023

[22] [22]

Zhenjian Lu and Igor C. Oliveira and Marius Zimand , title =. International Colloquium on Automata, Languages, and Programming , pages =

View on Pith

[23] [23]

Ming Li and Paul M. B. Vitanyi , title =

View on Pith

[24] [24]

Madhu Sudan , title =. J. Complex. , volume =. 1997 , url =. doi:10.1006/JCOM.1997.0439 , timestamp =

View on Pith doi:10.1006/jcom.1997.0439 1997

[25] [25]

Russell Impagliazzo and Avi Wigderson , title =. Symposium on Theory of Computing , pages =

View on Pith

[26] [26]

Raz, Ran and Reingold, Omer and Vadhan, Salil P. , title =. J. Comput. Syst. Sci. , volume =. 2002 , doi =

View on Pith 2002

[27] [27]

Shuichi Hirahara and Rahul Ilango and Zhenjian Lu and Mikito Nanashima and Igor C. Oliveira , title =. Symposium on Theory of Computing , pages =

View on Pith

[28] [28]

Russell Impagliazzo , title =. Conference on Computational Complexity , pages =

View on Pith

[29] [29]

Shuichi Hirahara and Mikito Nanashima , title =. Symposium on Foundations of Computer Science , pages =

View on Pith

[30] [30]

Rahul Ilango and Hanlin Ren and Rahul Santhanam , title =. Symposium on Theory of Computing , pages =

View on Pith

[31] [31]

Yanyi Liu and Rafael Pass , title =. Annual Cryptology Conference , pages =. 2023 , timestamp =. doi:10.1007/978-3-031-38545-2_21 , _bib2doi_selected =

View on Pith doi:10.1007/978-3-031-38545-2_21 2023

[32] [32]

Johan H. A Pseudorandom Generator from any One-way Function , journal =

View on Pith

[33] [33]

Shuichi Hirahara and Rahul Santhanam , title =. Innovations in Theoretical Computer Science Conference , pages =. 2022 , url =. doi:10.4230/LIPICS.ITCS.2022.85 , timestamp =

View on Pith doi:10.4230/lipics.itcs.2022.85 2022

[34] [34]

Meta-. Spring 2023 , url =

View on Pith 2023

[35] [35]

Zhenjian Lu and Igor C. Oliveira , title =. Bull. 2022 , url =

View on Pith 2022