Counting Martingales for Measure and Dimension in Complexity Classes

Adewale Sekoni; Hadi Shafei; John M. Hitchcock

REVIEW 5 major objections 4 minor 95 references

Counting Martingales for Measure and Dimension in Complexity Classes

T0 review · 5 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that for every $\alpha<1$, the subcircuit class $\mathrm{SIZE}((2^n/n)(1+\alpha \log n/n))$ has SpanP-measure zero—so almost every $\Delta_3^P$ language needs near-maximum circuits.

desk verdict A genuinely new framework for resource-bounded measure via counting classes, with a plausible but not-yet-closed proof of its main advertised transfer; worth refereeing, but the referee should push on Lemma 3.11. read the letter →

arxiv 2508.07619 v1 pith:5MRYI3OY submitted 2025-08-11 cs.CC

John M. Hitchcock , Adewale Sekoni , Hadi Shafei This is my paper

classification cs.CC

keywords countingmartingalesresource-boundedmeasureanddimensionSpanPGapcircuitlowerboundsminimumsizeproblemexponential-timehierarchyquantumcomplexityBPPBQP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a family of resource-bounded measures and dimensions built from counting functions—#P, SpanP, and GapP—rather than from deterministic time or space bounds, and shows how these intermediate notions settle statements that are open for polynomial-time measure. The headline result is that, for every $\alpha<1$, the class $X_\alpha$ of languages with circuits of size at most $(2^n/n)(1+\alpha\log n/n)$ has SpanP-measure 0; by the paper's transfer theorem, $X_\alpha$ also has $\Delta_3^P$-measure 0, so almost every problem in the third level of the exponential-time hierarchy has near-maximum circuit size. A reader should care because this moves the classical 1992 PSPACE-measure circuit lower bound into a weaker, third-level resource bound, and because the same counting-martingale toolbox yields zero-dimension results for BPP and BQP.

What carries the argument

The central object is the counting martingale: a martingale $d(w)=f(w,r)/g(w,r)$ in which $f$ is a #P, SpanP, or GapP function and $g$ is a polynomial-time power of two. Measure zero means some counting martingale succeeds on every member of the class. Two mechanisms carry the argument. First, the MCSP cover: the set of truth-table prefixes whose circuit complexity is below a stated bound is an NP language, and the conditional-probability martingale over that cover is exactly a SpanP counting martingale; Borel-Cantelli summation converts a convergent family of covers into a single succeeding martingale. Second, the approximation transfer: Theorem 3.12 converts a SpanP martingale into a $\Del

What would settle it

Check Lemma 3.11 at the identity approximation $f=g$ with $\epsilon_n=1/(n+1)$: the displayed inequality requires $(h(v0)/g(v0)+h(v1)/g(v1))\cdot((1-\epsilon_n)/(1+\epsilon_n))^{n+1}\le 2(h(v)/g(v))\cdot((1-\epsilon_n)/(1+\epsilon_n))^n$; evaluating this at a node where $d(v)=1$ shows whether the exponent closes, and if it fails for any $n$, the $\Delta_3^P$ transfer in Theorem 3.12 fails exactly there.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a transfer principle: many standard martingale constructions are ratios of counting functions, and replacing the deterministic resource bound on the martingale by a #P, SpanP, or GapP bound yields measures and dimensions intermediate between the polynomial-time and polynomial-space notions. The application that carries the paper is Theorem 6.1: the class $X_\alpha=\mathrm{SIZE}((2^n/n)(1+\alpha\log n/n))$, for any $\alpha<1$, has SpanP-measure 0. The proof builds a cover $A$ from the Minimum Circuit Size Problem (MCSP) — $A$ contains exactly the truth-table prefixes $B_{\le n}$ that have an $s(n)$-gate circuit — and bets with the cover marti

Load-bearing premise

The load-bearing premise is Theorem 3.12's claim that a SpanP-counting martingale can be converted, through the standard SpanP approximation theorem, into a $\Delta_3^P$-computable supermartingale that retains a constant fraction of its value; if that conversion fails—in particular, if the displayed supermartingale inequality in Lemma 3.11 does not close or no bridge from approximate to exact counting martingales exists—the main circuit-bound result collapses to the previousl

Editorial extensions

If this is right

For every $\alpha<1$, $X_\alpha=\mathrm{SIZE}((2^n/n)(1+\alpha\log n/n))$ has SpanP-measure 0 and, by Corollary 6.3, $\Delta_3^P$-measure 0, so the third-level class is not contained in the sub-$\alpha$ circuit class.
Under the paper's Derandomization Hypothesis 2.2, the same $X_\alpha$ has $\Delta_2^P$-measure 0, improving the circuit lower bound to the second level of the exponential hierarchy.
BPP has #P-dimension 0, BQP has GapP-dimension 0, and the class of languages with $o(2^n/n)$-size quantum circuits has GapP-strong-dimension 0, giving the resource-bounded dimension framework its first quantum complexity statements.
If one-way functions exist, there is a single sequence whose P-dimension and #P-dimension differ by nearly 1, so #P-dimension is a genuinely stronger measure than P-dimension under that assumption.
Counting random languages are bi-immune to the corresponding exponential-time classes, extending the known polynomial-time and space-bounded bi-immunity results.

Reading between the lines

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

Inference: if the $\Delta_3^P$ transfer in Theorem 3.12 is repaired, the same MCSP cover should yield the measure-zero statement at whatever level of the exponential hierarchy can approximate SpanP; a natural test is to apply the cover martingale directly to the constant-factor approximation, bypassing the exact-form bridge.
Inference: the acceptance-probability martingale suggests a general recipe—any language class defined by bounded-error machines with uniformly countable random seeds should have zero counting dimension with the corresponding gap-definable function; extending this to advice classes such as BPP/small is not automatic because the advice-dependent numerator may stop being GapP.
Inference: the one-way-function separation points to counting dimension as a quantitative witness for the difficulty of finding witnesses, so a plausible stronger statement—not made in the paper—is that average-case hardness assumptions separate not only P-dimension from #P-dimension but the full counting-dimension hierarchy.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real contribution here is the framework: counting martingales based on #P, SpanP, and GapP, with the accompanying notions of counting measure, dimension, and strong dimension. That is a genuinely new way to get intermediate notions between P and PSPACE, and the paper shows they can do real work. The MCSP-based cover for circuit-size lower bounds is clever, and the applications to BPP, BQP, and quantum circuit-size complexity are natural and interesting. If the main transfer result holds, the improvement of Lutz's 1992 genericity statement from ESPACE to the third level of the exponential hierarchy is a substantial step. The paper also engages honestly with prior work, and the self-citations are to published tools used in the intended direction.

The soft spots are real but not obviously fatal. Lemma 3.11 is the load-bearing piece: the displayed supermartingale inequality does not close with the exponent as written, and the claimed universal constant gamma does not follow from the algebra shown. On top of that, there is a missing bridge between the approximate counting martingales used in the measure-zero definitions and the exact counting martingales used in the transfer and Borel-Cantelli lemmas. As it stands, Corollary 6.3 is not established by the text given. I also noticed a few smaller issues: the counting computation in Theorem 6.1 looks off by a factor, the BPP machine parameters in Lemma 4.10 read garbled, and the inequality direction in Theorem 6.5 needs checking. None of these looks like a fundamental obstruction, and standard techniques may well repair them, but the write-up is rougher than it should be for a paper making this kind of claim. The OCR degradation of the manuscript adds uncertainty to any close reading of displayed equations, so I would not treat the specific algebra as final.

Bottom line: this paper is for complexity theorists working on resource-bounded measure and dimension, and for anyone interested in circuit lower bounds via generic nonuniformity. The framework deserves serious attention, and the results are likely correct in spirit. But the main transfer needs a clean proof before the central corollaries can be trusted. I would send it to a serious referee with that instruction, and I would expect a revision rather than a desk reject.

For the reading group: maybe. For citation: yes, if I work in this area.

Referee Report

5 major / 4 minor

Summary. The paper introduces counting martingales, whose values are given by ratios of functions in #P, SpanP, or GapP to polynomial-time powers of two, and uses them to define counting measures, dimensions, and strong dimensions. These notions are intermediate between polynomial-time and polynomial-space resource-bounded measure. The main advertised application is an improvement of Lutz's 1992 PSPACE-measure circuit lower bound: the class SIZE(2^n/n (1 + α log n / n)) is claimed to have SpanP-measure 0 for every α < 1, and hence to have measure 0 in Δ3^P. The proof passes through an entropy-rate measure M_NP defined via the Minimum Circuit Size Problem. The paper also proves several dimension results, including #P-dimension 0 for BPP, GapP-dimension 0 for BQP, and GapP-strong-dimension 0 for quantum SIZE(o(2^n/n)).

Significance. If the main results are correct, the paper gives a useful new framework that sits between P-measure and PSPACE-measure, unifies several known martingale constructions, and improves a decades-old circuit lower bound from ESPACE to the third level of the exponential hierarchy. The applications to quantum circuit complexity are also new to resource-bounded measure. The paper is well organized and the central intuition is clear. However, the most important transfer step, from SpanP-measure to Δ3^P-measure, has proof gaps that are load-bearing; the manuscript is not yet in a form where the main corollaries are established as written.

major comments (5)

[§3.5, Lemma 3.11] The proof does not close as written. The exponent k in the definition of d_n(v) is never specified, and the displayed supermartingale inequality appears to drop the factor (1+ε_n)/(1-ε_n) obtained in the approximation step. With a constant factor ((1-ε_n)/(1+ε_n))^k for all nodes, the inequality d_n(v0)+d_n(v1) ≤ 2 d_n(v) is not implied. A correct construction is possible, e.g. taking the factor to be ((1-ε_n)/(1+ε_n))^{|v|}, but it must be written out and verified. Since Theorem 3.12 and Corollary 6.3 rest on this lemma, this is a load-bearing gap.
[§3.1/§3.3 vs §3.4] Definition 3.3 defines counting measure zero using approximate counting martingales (Definition 3.1(1)), but the summation lemma, the two Borel-Cantelli lemmas, and Lemma 3.11 are all stated for exact counting martingales (Definition 3.1(2)). No lemma is supplied converting an approximate counting martingale into an exact one with the same success set and resource bound. This matters because Theorem 3.12, which is the bridge to Δ3^P-measure, is proved only for exact SpanP-martingales. The definitions or the proof strategy must be made consistent.
[§3.5, Theorem 3.12] Even granting Lemma 3.11, the theorem concludes Δ3^P-measure 0 from a Δ3^P-computable supermartingale d' satisfying d' ≥ γ d. The paper cites the general martingale/supermartingale equivalence [5] only in Section 2.1, but it does not show that the conversion can be performed within Δ3^P, nor does it redefine measure zero to allow supermartingales. This conversion is essential for Corollary 6.3 and should be justified explicitly.
[§6.1, Theorem 6.1] The counting argument contains an arithmetically inconsistent display. The proof writes log |A_{=n}| < Σ_{i=1}^{s(n)} 2^i + log(48 e s(n))^{s(n)} and then equates this with 2^n - 1 + s(n)(log(48e)+log s(n)). If the sum really runs from 1 to s(n), the first term is 2^{s(n)+1}, not 2^n - 1; if a different sum is intended, it should be stated. The correct bound should come from the number of circuits of size at most s(n), of the form (c s(n))^{s(n)}, and the proof should show that this yields the claimed function f(N) with the required convergence.
[§6.2, Theorem 6.10] The proof that QSIZE(o(2^n/n)) has GapP-strong-dimension 0 needs more detail. The function g^{n0,b}(x) is defined by summing the real-valued Acceptance Probability martingale d^{n0,b}(w) over extensions and over guessed quantum circuit vectors. To obtain an exact GapP-martingale d^{n0,b}=g/h, one must represent each acceptance probability as a GapP function divided by a power of 2 uniformly for all circuits in the guessed family, and one must specify h_n(x) precisely. These points are only sketched, so the claimed GapP-strong-dimension result is not yet fully supported.

minor comments (4)

[§3.5, Lemma 3.11] The exponent k is undefined in the statement of the lemma; please define it explicitly (for example k=|v| or k=|v|-1) before the proof.
[§3.5, Theorems 3.13 and 3.14] The phrase 'The following two theorems and their corollaries' appears before a single theorem block; the numbering and cross-references should be checked.
[§5.2, Definition 5.7] The numbered list has two items labeled '1.' and two labeled '2.'; the numbering should be corrected.
[§6.1, Theorem 6.1] The notation N is used both for the total number of strings of length at most n and in the function f(N); please clarify the mapping between n and N in the displayed formulas.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main circuit-size and dimension theorems are proved by explicit martingale constructions reducing to external results; reliance on authors' prior theorems is forward use, not definitional.

full rationale

The paper's derivation chain is not circular. The counting martingale, counting measure, and counting dimension notions (Definitions 3.1-3.3) are genuinely new definitions, and the main results are established by explicit martingale constructions (Cover, Conditional Expectation, Acceptance Probability, Bi-immunity) that reduce target classes to known external facts: Lutz's counting bound, the KST approximation of SpanP by Delta_2^P functions, Fortnow-Rogers' BPP/BQP containments, and the independent Nandakumar et al. one-way-function separation. The central transfer theorem (Theorem 3.12) converts a SpanP-martingale into a Delta_3^P-supermartingale via the KST approximation; this is a resource reduction, not an identification of premise and conclusion. The paper does cite the authors' own prior work (e.g., Hitchcock-Vinodchandran entropy rates, Athreya et al. strong dimension) for lower bounds and comparisons, but these are parameter-free, published, externally falsifiable theorems used forward; they do not define the target results. No fitted parameter is renamed as a prediction, and no uniqueness conclusion is imported by self-citation. Two proof gaps identified by a careful reading are correctness concerns, not circularity: (i) Lemma 3.11's supermartingale inequality requires a precise choice of exponent (k=|v|) to close, and the OCR text leaves this ambiguous; (ii) Definition 3.3 uses approximable counting martingales while Lemma 3.11 and the Borel-Cantelli lemmas are stated for exact counting martingales, with no explicit bridge between the two. Neither gap makes a result true by construction or reduces a prediction to an input, so the circularity score remains low.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The count above is the paper's honest input bill. The framework itself is cheap: the central claims rest on standard martingale characterizations, standard counting-complexity tools, and two external facts (MCSP ∈ NP; counting of quantum circuits). The structural risks are concentrated in the unstated exact or approximate conversion axiom and in the constants chosen inside Lemma 3.11 for the approximation. There are no fitted parameters with empirical content.

free parameters (4)

α (in X_α, D_α, SIZE^io classes) = universal parameter, not fitted
Labels the circuit-size bound (2^n/n)(1 + α log n / n) and the classes SIZE(α 2^n/n); all results hold for every α in the stated range, so it is a quantifier, not a fit.
slack constant γ (Lemma 3.11) = any value in (0, 1/e²)
Introduced by hand to absorb the approximation factor ((1-ε)/(1+ε))^n in the SpanP to Δ₃^P martingale transfer; has no empirical content and does not affect the transfer theorem.
ε_n = 1/n (Lemma 3.11) = 1/n
Chosen to make the SpanP-approximation supermartingale inequality close; if the intended exponent is |v| rather than n, the choice must change, which is exactly where the written proof is fragile.
δ_b = c/n^b (Theorem 6.10) = c/n^b, b ≥ 1 arbitrary
Hand-chosen slack in the quantum circuit-counting bound; letting b go to infinity drives the GapP-strong-dimension bound to 0.

assumptions (7)

standard math Martingale characterizations of Lebesgue measure 0, Hausdorff dimension, and packing dimension (Ville 1939, Lutz 2003, Athreya et al. 2007)
Invoked via Definitions 2.3 and Proposition 3.2 to justify that martingale-based counting measures inherit classical measure and dimension semantics.
standard math Closure properties and inclusions of #P, SpanP, GapP (Valiant; Köbler-Schöning-Toran; Fenner-Fortnow-Kurtz)
Used in Lemmas 3.5 to 3.9 (summation and union lemmas) and in Constructions 4.1, 4.3, 4.5, 4.9 to certify numerators are in the right counting class.
standard math Köbler-Schöning-Toran approximation of SpanP functions by FP^{Σ₂^P} computable functions (Theorem 2.1), and the Shaltiel-Umans derandomized version (Theorem 2.3)
Load-bearing for Lemma 3.11 and hence Theorems 3.12 and 3.14, the step that moves SpanP-measure 0 to the exponential-time hierarchy levels.
domain assumption MCSP ∈ NP, with truth tables encoded as strings (Kabanets-Cai)
Used in Theorem 6.1 to place the cover A in NP so the cover martingale is a SpanP-martingale.
domain assumption Counting of small quantum circuits: for a fixed universal gate set, the number of size-s quantum circuits is at most 2^{c·s·n} (Chia et al. [18])
The entropy-rate engine of Theorem 6.10 (GapP-strong-dimension 0 for quantum SIZE o(2^n/n)).
domain assumption BQP ⊆ AWPP (Fortnow-Rogers) and polynomial-time amplification of quantum and classical bounded-error machines
Gives the GapP acceptance-probability martingale of Theorem 4.12; the amplification schedule is where Lemma 4.10's stated parameters overreach for polynomial-time BPP.
ad hoc to paper Every approximately computable counting martingale (Definition 3.1(1)) may be replaced by an exact counting martingale (Definition 3.1(2)) with the same success set and resource bound
Unstated but needed: measure zero (Definition 3.2) is defined with approximate martingales while Lemma 3.8 and Lemma 3.11 require exact ones; the paper supplies no conversion lemma.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Counting Martingales for Measure and Dimension in Complexity Classes." pith.science (2026). https://pith.science/paper/5MRYI3OY

@misc{pith2026250807619,
  author       = {Pith},
  title        = {Pith review of: Counting Martingales for Measure and Dimension in Complexity Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5MRYI3OY}},
  note         = {Machine review of arXiv:2508.07619}
}

abstract

This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds. Resource-bounded measure and dimension have traditionally focused on deterministic time and space bounds. We use counting complexity classes to develop resource-bounded counting measures and dimensions. Counting martingales are constructed using functions from the #P, SpanP, and GapP complexity classes. We show that counting martingales capture many martingale constructions in complexity theory. The resulting counting measures and dimensions are intermediate in power between the standard time-bounded and space-bounded notions, enabling finer-grained analysis where space-bounded measures are known, but time-bounded measures remain open. For example, we show that BPP has #P-dimension 0 and BQP has GapP-dimension 0. As our main application, we improve circuit-size lower bounds. Lutz (1992) strengthened Shannon's classic $(1-\epsilon)\frac{2^n}{n}$ lower bound (1949) to PSPACE-measure, showing that almost all problems require circuits of size $\frac{2^n}{n}\left(1+\frac{\alpha \log n}{n}\right)$, for any $\alpha < 1$. We extend this result to SpanP-measure, with a proof that uses a connection through the Minimum Circuit Size Problem (MCSP) to construct a counting martingale. Our results imply that the stronger lower bound holds within the third level of the exponential-time hierarchy, whereas previously, it was only known in ESPACE. We study the #P-dimension of classical circuit complexity classes and the GapP-dimension of quantum circuit complexity classes. We also show that if one-way functions exist, then #P-dimension is strictly more powerful than P-dimension.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

95 extracted references · 79 canonical work pages

[5]

Ambos-Spies, H.-C

K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. �� , 168(1):3–19, 1996. �� . 10

1996
[1]

Aaronson, B

S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Technical Report TR10-174, Electronic Colloquium on Computational Complexity, 2010. 34

2010
[2]

Oracles are subtle but not malicious

Scott Aaronson. Oracles are subtle but not malicious. In �� , pages 340–354. IEEE Computer Society, 2006. �� , �� . 38, 40

2006
[3]

Allender and R

E. Allender and R. Rubinstein. P-printable sets. �� , 17:1193–1202,
[4]

Ambos-Spies and E

K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In A. Sorbi, editor, �� , Lecture Notes in Pure and Applied Mathe- matics, pages 1–47. Marcel Dekker, New York, N.Y., 1997. �� . 3, 4, 9

1997
[6]

��

Sanjeev Arora and Boaz Barak. �� . Cambridge University Press, 2009. 9

2009
[7]

Grilo, Tom Gur, Igor C

Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. In �� , pages 562–573. IEEE, 2021. �� . 24

2021
[8]

Arvind and J

V. Arvind and J. K¨ obler. On pseudorandomness and resource-bounded measure. �� , 255(1–2):205–221, 2001. �� . 39

2001

Show all 95 references

[9]

K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Effective strong dimen- sion in algorithmic information and computational complexity. �� , 37(3):671–705, 2007. �� , �� . 3, 4, 5, 9, 13, 25, 35

2007
[10]

Aydinlioglu, D

B. Aydinlioglu, D. Gutfreund, J. M. Hitchcock, and A. Kawachi. Derandomizing Arthur- Merlin games and approximate counting implies exponential-size lower bounds. �� , 20(2):329–366, 2011. �� . 34

2011
[11]

Quantum analog of Shannon’s lower bound theorem

Saugata Basu and Laxmi Parida. Quantum analog of Shannon’s lower bound theorem. Tech- nical Report 2308.13091, arXiv, 2023. �� . 36

2023 arXiv
[12]

Berman and J

L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. �� , 6(2):305–322, 1977. �� . 38, 45

1977
[13]

R. V. Book. Tally languages and complexity classes. �� , 26:186–193,
[14]

Buhrman, L

H. Buhrman, L. Fortnow, J. M. Hitchcock, and B. Loff. Learning reductions to sparse sets. In �� , pages 243–253. Springer-Verlag, 2013. �� . 38 41

2013
[15]

Buhrman and S

H. Buhrman and S. Homer. Superpolynomial circuits, almost sparse oracles and the expo- nential hierarchy. In �� , pages 116–127. Springer, 1992. �� . 38

1992
[16]

Symmetric exponential time requires near- maximum circuit size

Lijie Chen, Shuichi Hirahara, and Hanlin Ren. Symmetric exponential time requires near- maximum circuit size. In �� , STOC 2024, page 1990–1999, New York, NY, USA, 2024. Association for Com- puting Machinery. ��...

2024
[17]

Quantum meets the minimum circuit size problem

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum meets the minimum circuit size problem. Technical Report 2108.03171, arXiv, 2021. �� . 36

2021 arXiv
[18]

Quantum Meets the Minimum Circuit Size Problem

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In Mark Braverman, editor, �� , volume 215 of �� ...

2022
[19]

Downey and D

R. Downey and D. Hirschfeldt. �� . Springer-Verlag,
[20]

S. A. Fenner, L. Fortnow, and S. A. Kurtz. Gap-definable counting classes. �� , 48(1):116–148, 1994. �� . 3, 6, 11, 24, 40

1994
[21]

An oracle builder’s toolkit

Stephen Fenner, Lance Fortnow, Stuart A Kurtz, and Lide Li. An oracle builder’s toolkit. �� , 182(2):95–136, 2003. �� . 24

2003
[22]

Stephen A. Fenner. PP-lowness and a simple definition of A WPP. �� , 36(3):199–212, 2003. �� . 24

2003
[23]

L. Fortnow. Counting complexity. In L. A. Hemaspaandra and A. L. Selman, editors, �� , pages 81–107. Springer-Verlag, 1997. �� . 3

1997
[24]

Fortnow and J

L. Fortnow and J. Rogers. Complexity limitations on quantum computation. �� , 59(2):240–252, 1999. �� . 22, 24

1999
[25]

One complexity theorist’s view of quantum computing

Lance Fortnow. One complexity theorist’s view of quantum computing. �� , 292(3):597–610, 2003. �� . 22

2003
[26]

Reviewing bounds on the circuit size of the hardest functions

Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions. �� , 95(2):354–357, 2005. �� . 7, 35

2005
[27]

B. Fu. With quasilinear queries EXP is not polynomial time Turing reducible to sparse sets. �� , 24(5):1082–1090, 1995. �� . 8, 38

1995
[28]

X. Gu. A note on dimensions of polynomial size circuits. �� , 359(1–3):176–187, 2006. �� . 36 42

2006
[29]

Harkins and John M

Ryan C. Harkins and John M. Hitchcock. Dimension, halfspaces, and the density of hard sets. �� , 49(3):601–614, 2011. �� . 38

2011
[30]

Hausdorff

F. Hausdorff. Dimension und ¨ außeres Maß. �� , 79:157–179, 1919. �� . 4, 12

1919
[31]

J. M. Hitchcock. �� . PhD thesis, Iowa State University, 2003. URL: �� . 7, 28, 31

2003
[32]

J. M. Hitchcock. The size of SPP. �� , 320(2–3):495–503, 2004. �� . 39

2004
[33]

J. M. Hitchcock. Correspondence principles for effective dimensions. �� , 38(5):559–571, 2005. �� . 28

2005
[34]

J. M. Hitchcock. Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. �� , 36(6):1696–1708, 2007. �� , �� . 8, 38

2007
[35]

J. M. Hitchcock, M. L´ opez-Vald´ es, and E. Mayordomo. Scaled dimension and the Kolmogorov complexity of Turing-hard sets. �� , 43(3-4):471–497, 2008. �� . 4

2008
[36]

J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Scaled dimension and nonuniform complexity. �� , 69(2):97–122, 2004. �� . 32

2004
[37]

J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. The fractal geometry of complexity classes. �� , 36(3):24–38, September 2005. �� . 3, 4, 9

2005
[38]

J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. �� , 17(1):119–146, 2008. �� . 40

2008
[39]

J. M. Hitchcock and A. Pavan. On the NP-completeness of the minimum circuit size problem. In �� , pages 236–245. Leibniz International Proceedings in Informatics,
[40]

J. M. Hitchcock and N. V. Vinodchandran. Dimension, entropy rates, and compression.�� , 72(4):760–782, 2006. �� . 4, 7, 8, 9, 10, 11, 27, 28, 31, 32, 35, 36

2006
[41]

Impagliazzo and A

R. Impagliazzo and A. Wigderson. Randomness vs. time: Derandomization under a uniform assumption. �� , 63:672–688, 2001. �� . 22

2001
[42]

D. W. Juedes and J. H. Lutz. Weak completeness in E and E �. �� , 143(1):149–158, 1995. �� . 13

1995
[43]

D. W. Juedes and J. H. Lutz. Completeness and weak completeness under polynomial-size circuits. �� , 125(1):13–31, 1996. �� . 4 43

1996
[44]

Kabanets and J.-Y

V. Kabanets and J.-Y. Cai. Circuit minimization problem. In �� , pages 73–79. ACM, 2000. �� . 7, 33

2000
[45]

R. M. Karp and R. J. Lipton. Turing machines that take advice. �� , 28:191–201, 1982. �� . 38

1982
[46]

K¨ obler, U

J. K¨ obler, U. Sch¨ oning, and J. Toran. On counting and approximation. �� , 26(4):363–379, 1989. �� . 3, 10

1989
[47]

The hardest explicit construction

Oliver Korten. The hardest explicit construction. In �� , pages 433–444. IEEE, 2022. �� . 7, 36

2022
[48]

W. Kuich. On the entropy of context-free languages. �� , 16:173–200,
[49]

Int´ egrale, longueur, aire

Henri Lebesgue. Int´ egrale, longueur, aire. �� , 7(1):231– 359, 1902. �� . 4, 12

1902
[50]

��

Lide Li. �� . PhD thesis, University of Chicago, 1993. URL: �� . 3, 11

1993
[51]

Symmetric exponential time requires near-maximum circuit size: Simplified, truly uniform

Zeyong Li. Symmetric exponential time requires near-maximum circuit size: Simplified, truly uniform. In �� , STOC 2024, page 2000–2007, New York, NY, USA, 2024. Association for Computing Machinery. ��...

2024
[52]

O. B. Lupanov. On the synthesis of contact networks. �� , 119(1):23–26, 1958. 3, 7

1958
[53]

J. H. Lutz. �� . PhD thesis, California Institute of Technology, 1987. �� . 3

1987
[54]

J. H. Lutz. Category and measure in complexity classes. �� , 19(6):1100–1131, 1990. ��

1990
[55]

J. H. Lutz. Almost everywhere high nonuniform complexity. �� , 44(2):220–258, 1992. �� . 3, 4, 5, 7, 9, 12, 15, 16, 30, 33, 34, 36

1992
[56]

J. H. Lutz. The quantitative structure of exponential time. In L. A. Hemaspaandra and A. L. Selman, editors, �� , pages 225–254. Springer-Verlag, 1997. �� . 3, 4, 9, 22, 40

1997
[57]

J. H. Lutz. Dimension in complexity classes. �� , 32(5):1236–1259,
[58]

J. H. Lutz. Effective fractal dimensions. �� , 51(1):62–72, 2005. �� . 4, 9 44

2005
[59]

J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. �� , 23(4):762–779, 1994. �� . 8, 38

1994
[60]

J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. �� , 164(1–2):141–163, 1996. �� . 40

1996
[61]

J. H. Lutz and E. Mayordomo. Twelve problems in resource-bounded measure. �� , 68:64–80, 1999. Also appears as [ � ]. 3, 4, 9, 40

1999
[62]

J. H. Lutz and Y. Zhao. The density of weakly complete problems under adaptive reductions. �� , 30(4):1197–1210, 2000. �� . 8, 38

2000
[63]

S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. �� , 25(2):130–143, 1982. �� . 38

1982
[64]

Mayordomo

E. Mayordomo. Almost every set in exponential time is P-bi-immune. �� , 136(2):487–506, 1994. �� . 7, 25, 26

1994
[65]

Mayordomo

E. Mayordomo. �� . PhD thesis, Univer- sitat Polit` ecnica de Catalunya, 1994. URL:�� . 4, 9, 33

1994
[66]

Mayordomo

E. Mayordomo. Effective Hausdorff dimension. In B. L¨ owe, B. Piwinger, and T. R¨ asch, editors, �� , vol- ume 23 of �� , pages 171–186. Kluwer Academic Press, 2004. �� ...

2004
[67]

Mayordomo

E. Mayordomo. Effective fractal dimension in algorithmic information theory. In S. B. Cooper, B. L¨ owe, and A. Sorbi, editors,�� , pages 259–285. Springer-Verlag, 2008. �� . 4, 9

2008
[68]

A. R. Meyer, 1977. Reported in [12]. 38

1977
[69]

P. B. Miltersen, N. V. Vinodchandran, and O. Watanabe. Superpolynomial versus subex- ponential circuit size in the exponential hierarchy. In �� , pages 210–220, 1999. �� . 7

1999
[70]

Murray and R

Cody D. Murray and R. Ryan Williams. On the (non) NP-hardness of computing circuit complexity. �� , 13(4):1–22, 2017. �� . 33

2017
[71]

One-way functions and polynomial time dimension

Satyadev Nandakumar, Subin Pulari, Akhil S, and Suronjona Sarma. One-way functions and polynomial time dimension. Technical Report 2411.02392, arXiv, 2025. �� . 7, 32

2025 arXiv
[72]

Ogiwara and O

M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. �� , 20(3):471–483, 1991. �� . 38 45

1991
[73]

K. W. Regan, D. Sivakumar, and J. Cai. Pseudorandom generators, measure theory, and natural proofs. In �� , pages 26–35. IEEE Computer Society, 1995. �� . 22

1995
[74]

C. A. Rogers. �� . Cambridge University Press, 1998. Originally published in 1970. 28

1998
[75]

The power of counting

Uwe Sch¨ oning. The power of counting. In Alan L. Selman, editor, �� , pages 204–223. Springer, 1990. �� . 3

1990
[76]

Shaltiel and C

R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. In �� , pages 212–226. IEEE Computer Society, 2005. �� . 10, 11

2005
[77]

C. E. Shannon. The synthesis of two-terminal switching circuits. �� , 28(1):59–98, 1949. �� . 3, 7

1949
[78]

L. Staiger. Recursive automata on infinite words. In �� , pages 629–639. Springer-Verlag, 1993. �� . 28

1993
[79]

L. J. Stockmeyer. On approximation algorithms for #P. �� , 14:849– 861, 1985. �� . 4, 10, 33

1985
[80]

Donald M. Stull. Resource bounded randomness and its applications. In Johanna N. Y. Franklin and Christopher P. Porter, editors,�� , volume 50 of �� , page 301–348. Cambridge University Press, Cambridge,
[81]

PP is as hard as the polynomial-time hierarchy

Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. �� , 20(5):865–877, 1991. �� . 16, 18

1991
[82]

C. Tricot. Two definitions of fractional dimension. �� , 91:57–74, 1982. 12

1982
[83]

The complexity of computing the permanent

Leslie G Valiant. The complexity of computing the permanent. �� , 8(2):189–201, 1979. �� . 3, 10

1979
[84]

van Melkebeek

D. van Melkebeek. The zero-one law holds for BPP. �� , 244(1– 2):283–288, 2000. �� . 22

2000
[85]

J. Ville. �� . Gauthier–Villars, Paris, 1939. 4, 13

1939
[86]

Watanabe

O. Watanabe. Polynomial time reducibility to a set of small density. In �� , pages 138–146. IEEE Computer Society,
[87]

C. B. Wilson. Relativized circuit complexity. �� , 31(2):169–181, 1985. �� . 38 46

1985
[1970]

�� . 27
[1974]

�� . 16
[1987]

�� . 38
[1988]

�� . 4
[2003]

3, 4, 5, 8, 9, 12, 13, 15, 34, 35, 38

�� , �� . 3, 4, 5, 8, 9, 12, 13, 15, 34, 35, 38
[2010]

�� . 4
[2015]

�� . 33
[2020]

�� . 4, 9

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [5]

Ambos-Spies, H.-C

K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. �� , 168(1):3–19, 1996. �� . 10

1996

[2] [1]

Aaronson, B

S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Technical Report TR10-174, Electronic Colloquium on Computational Complexity, 2010. 34

2010

[3] [2]

Oracles are subtle but not malicious

Scott Aaronson. Oracles are subtle but not malicious. In �� , pages 340–354. IEEE Computer Society, 2006. �� , �� . 38, 40

2006

[4] [3]

Allender and R

E. Allender and R. Rubinstein. P-printable sets. �� , 17:1193–1202,

[5] [4]

Ambos-Spies and E

K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In A. Sorbi, editor, �� , Lecture Notes in Pure and Applied Mathe- matics, pages 1–47. Marcel Dekker, New York, N.Y., 1997. �� . 3, 4, 9

1997

[6] [6]

��

Sanjeev Arora and Boaz Barak. �� . Cambridge University Press, 2009. 9

2009

[7] [7]

Grilo, Tom Gur, Igor C

Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. In �� , pages 562–573. IEEE, 2021. �� . 24

2021

[8] [8]

Arvind and J

V. Arvind and J. K¨ obler. On pseudorandomness and resource-bounded measure. �� , 255(1–2):205–221, 2001. �� . 39

2001