Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time

John M. Hitchcock

arxiv: 2605.03306 · v1 · submitted 2026-05-05 · 💻 cs.CC

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time

John M. Hitchcock This is my paper

Pith reviewed 2026-05-07 12:41 UTC · model grok-4.3

classification 💻 cs.CC

keywords circuit complexityresource-bounded categorysymmetric exponential timemeagernessBanach-Mazur gamerange avoidancealternation

0 comments

The pith

Languages requiring exponential-size circuits form the typical set in symmetric exponential time.

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

The paper defines a resource-bounded version of category for the class S^E_2 by using single-valued FS^P_2 strategies as moves in the Banach-Mazur game. It then shows that Li's algorithm for the range-avoidance problem supplies a winning strategy for the second player. This proves that the set of languages computable by circuits of size 2^n/n is meager inside S^E_2. Consequently, languages whose circuit complexity exceeds 2^n/n are comeager, meaning they constitute the generic or typical objects within the class under this measure of typicality.

Core claim

By extending resource-bounded category to S^E_2 via single-valued FS^P_2 strategies in the Banach-Mazur game, Li's FS^P_2 algorithm for range avoidance supplies a winning strategy that makes SIZE(2^n/n) meager in S^E_2. Therefore languages requiring circuits larger than 2^n/n are comeager in S^E_2 and can be regarded as typical with respect to this resource-bounded notion of category.

What carries the argument

Meagerness in S^E_2 defined by the existence of a winning single-valued FS^P_2 strategy for the second player in the Banach-Mazur game on the space of languages.

If this is right

The circuit-size lower bound 2^n/n holds for a comeager set of languages inside S^E_2.
Resource-bounded category notions can be lifted from ESPACE to symmetric alternation classes such as S^E_2.
The range-avoidance problem supplies a concrete winning strategy that forces exponential circuit size on typical members of S^E_2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same game-based argument could be checked for other symmetric classes to see whether exponential circuit size becomes typical there as well.
If the strategy can be derandomized or simplified, it might yield an explicit construction of hard languages inside S^E_2.

Load-bearing premise

The chosen definition of meagerness using single-valued FS^P_2 strategies correctly captures what it means for a set to be typical inside S^E_2.

What would settle it

An explicit dense collection of languages inside S^E_2 that all have circuits of size at most 2^n/n and on which no single-valued FS^P_2 strategy can force the second player to win the Banach-Mazur game.

read the original abstract

Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$. In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li's $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that SIZE($\frac{2^n}{n}$) is meager in $S^E_2$. Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note extends resource-bounded category from ESPACE to S^E_2 and claims SIZE(2^n/n) is meager there by turning Li's range-avoidance algorithm into a winning strategy.

read the letter

The punchline is that the paper gives a new definition of meagerness tailored to S^E_2 and uses it to conclude that languages needing circuits of size 2^n/n are comeager in that class. It does this by showing Li's FS^P_2 algorithm supplies a winning strategy in the corresponding Banach-Mazur game on languages in S^E_2. That is the actual advance over Lutz's 1987 result and Li's 2024 circuit lower bound for S^E_2. The write-up is direct: it states the prior results, introduces the single-valued FS^P_2 strategy notion, and asserts the reduction without extra layers. That keeps the note short and focused. The part that works cleanly is the linkage to an existing algorithm rather than inventing new machinery. The soft spot sits in the central claim. The abstract says the algorithm yields a winning strategy, but turning finite-prefix responses into a single-valued FS^P_2 function that always forces the constructed language outside every 2^n/n circuit, against any opponent moves, requires careful resource accounting. If that translation holds without hidden exponential blowups or loss of single-valuedness, the result follows. If not, the meagerness statement does not go through. The paper is aimed at readers who already track resource-bounded category and measure results in exponential classes. Someone working on typicality or on S^E_2 properties will see the incremental step right away. It is narrow enough that a general audience will not get much, but the claim is precise enough to be worth checking. I would send it to peer review. The extension is modest but the target class is natural, and a referee can verify the game-strategy construction in one pass.

Referee Report

1 major / 1 minor

Summary. The paper extends resource-bounded category to the symmetric exponential time class S^E_2 by defining meagerness relative to single-valued FS^P_2 strategies in the Banach-Mazur game. It claims that Li's (2024) FS^P_2 algorithm for the Range Avoidance problem supplies a winning strategy in this game, which implies that SIZE(2^n/n) is meager in S^E_2. Consequently, languages requiring circuits larger than 2^n/n are comeager in S^E_2.

Significance. If the reduction from Li's algorithm to a winning strategy holds, the result supplies a resource-bounded notion of typicality for circuit complexity inside S^E_2 and shows that exponential circuit lower bounds are the generic case under this category. It directly connects an existing algorithmic result on range avoidance to a category-theoretic statement, extending Lutz's framework in a natural way.

major comments (1)

[Main argument (Li's algorithm yields a winning strategy)] The central step asserting that Li's FS^P_2 Range Avoidance algorithm yields a single-valued winning strategy in the FS^P_2 Banach-Mazur game on S^E_2 languages (the argument immediately following the game definition) lacks an explicit construction. It is unclear how the algorithm, when applied to finite prefixes, produces responses that remain single-valued, stay within FS^P_2, and force the constructed language to differ from every circuit of size 2^n/n against arbitrary opponent moves. This translation is load-bearing for the meagerness claim.

minor comments (1)

[Abstract] The classes S^E_2 and FS^P_2 are used without an inline definition or pointer to a standard reference on first appearance in the abstract and introduction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need for greater clarity in the central argument. We have revised the paper to address this point directly.

read point-by-point responses

Referee: [Main argument (Li's algorithm yields a winning strategy)] The central step asserting that Li's FS^P_2 Range Avoidance algorithm yields a single-valued winning strategy in the FS^P_2 Banach-Mazur game on S^E_2 languages (the argument immediately following the game definition) lacks an explicit construction. It is unclear how the algorithm, when applied to finite prefixes, produces responses that remain single-valued, stay within FS^P_2, and force the constructed language to differ from every circuit of size 2^n/n against arbitrary opponent moves. This translation is load-bearing for the meagerness claim.

Authors: We agree that the original manuscript presented the translation from Li's algorithm to a winning strategy at too high a level and did not supply an explicit construction. In the revised version we have inserted a detailed construction immediately after the game definition. The construction proceeds by using Li's deterministic single-valued FS^P_2 procedure on the finite set of circuits of size 2^n/n that are consistent with the current prefix; the output of the procedure supplies the next move of the strategy. Because the procedure is deterministic and single-valued, the resulting strategy remains single-valued and lies in FS^P_2. By design, each extension produced by the procedure ensures that the infinite language eventually differs from every circuit of size 2^n/n, regardless of the sequence of moves chosen by the opponent. We believe this addition makes the argument fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on external results

full rationale

The paper defines meagerness for S^E_2 via single-valued FS^P_2 Banach-Mazur strategies as an extension of Lutz (1987), then invokes Li (2024)'s independent FS^P_2 Range Avoidance algorithm to obtain the winning strategy. No self-citation load-bearing, no fitted parameters renamed as predictions, no ansatz smuggled via citation, and no reduction of the comeager claim to the paper's own inputs by construction. The central step is an application of an external algorithm to the newly defined game, which remains self-contained against the cited benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities introduced. Relies on standard mathematical axioms of complexity theory, topology, and the prior definitions of resource-bounded category and S^E_2.

axioms (1)

standard math Standard axioms and definitions of resource-bounded category from Lutz 1987 and complexity class S^E_2
The paper extends these established frameworks without new postulates.

pith-pipeline@v0.9.0 · 5449 in / 1111 out tokens · 106552 ms · 2026-05-07T12:41:54.200849+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

[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. 1

2010
[2]

Aydinlioglu, D

B. Aydinlioglu, D. Gutfreund, J. M. Hitchcock, and A. Kawachi. Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds.Computational Complexity, 20(2):329–366, 2011.doi:10.1007/s00037-011-0010-8

work page doi:10.1007/s00037-011-0010-8 2011
[3]

Nonrelativizing separations

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing separations. InProceedings of the 13th Annual IEEE Conference on Computational Complexity, pages 8–12. IEEE Computer Society, 1998. doi:10.1109/CCC.1998.694585. 1

work page doi:10.1109/ccc.1998.694585 1998
[4]

Procedia CIRP72(March), 159–164 (2018) https://doi.org/10.1016/j

Jin-yi Cai.S p 2 ⊆ZPP NP.Journal of Computer and System Sciences, 73(1):25–35, 2007.doi:10.1016/J. JCSS.2003.07.015. 2, 4

work page doi:10.1016/j 2007
[5]

More on BPP and the polynomial-time hierarchy.Information Processing Letters, 57(5):237–241, 1996.doi:10.1016/0020-0190(96)00016-6

Ran Canetti. More on BPP and the polynomial-time hierarchy.Information Processing Letters, 57(5):237–241, 1996.doi:10.1016/0020-0190(96)00016-6. 1, 2

work page doi:10.1016/0020-0190(96)00016-6 1996
[6]

InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing(Vancouver, BC, Canada)(STOC 2024).AssociationforComputingMachinery,NewYork,NY,USA,1816–1819

Lijie Chen, Shuichi Hirahara, and Hanlin Ren. Symmetric exponential time requires near-maximum cir- cuit size. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1990–1999, New York, NY , USA, 2024. Association for Computing Machinery.doi:10.1145/3618260. 3649624. 1, 3, 4

work page doi:10.1145/3618260 2024
[7]

Reviewing bounds on the circuit size of the hardest functions.Information Processing Letters, 95(2):354–357, 2005.doi:10.1016/j.ipl.2005.03.009

Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions.Information Processing Letters, 95(2):354–357, 2005.doi:10.1016/j.ipl.2005.03.009. 3

work page doi:10.1016/j.ipl.2005.03.009 2005
[8]

J. M. Hitchcock, A. Sekoni, and H. Shafei. Counting martingales for measure and dimension in complexity classes. InProceedings of the 40th Computational Complexity Conference (CCC 2025), volume 339 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:35, 2025.doi:10.4230/LIPIcs.CCC. 2025.20. 3

work page doi:10.4230/lipics.ccc 2025
[9]

J. M. Hitchcock and N. V . Vinodchandran. Dimension, entropy rates, and compression.Journal of Computer and System Sciences, 72(4):760–782, 2006.doi:10.1016/j.jcss.2005.10.002. 1

work page doi:10.1016/j.jcss.2005.10.002 2006
[10]

R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets.Information and Control, 55(1- 3):40–56, 1982.doi:10.1016/s0019-9958(82)90382-5. 1, 4

work page doi:10.1016/s0019-9958(82)90382-5 1982
[11]

Klivans and D

A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses.SIAM Journal on Computing, 31(5):1501–1526, 2002.doi:10.1137/ s0097539700389652. 4 5

2002
[12]

The hardest explicit construction

Oliver Korten. The hardest explicit construction. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 433–444. IEEE, 2022.doi:10.1109/FOCS52979.2021.00051. 1, 3

work page doi:10.1109/focs52979.2021.00051 2022
[13]

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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 2000–2007, New York, NY , USA, 2024. Association for Computing Machinery.doi:10.1145/3618260.3649615. 1, 3

work page doi:10.1145/3618260.3649615 2024
[14]

J. H. Lutz. Resource-bounded Baire category and small circuits in exponential space. InProceedings of the Second Structure in Complexity Theory Conference, pages 81–91. IEEE Computer Society Press, 1987. doi:10.1109/psct.1987.10319257. 1, 2, 4

work page doi:10.1109/psct.1987.10319257 1987
[15]

J. H. Lutz.Resource-Bounded Category and Measure in Exponential Complexity Classes. PhD thesis, Califor- nia Institute of Technology, 1987.doi:10.7907/qny92-v6h14

work page doi:10.7907/qny92-v6h14 1987
[16]

J. H. Lutz. Category and measure in complexity classes.SIAM Journal on Computing, 19(6):1100–1131, 1990. doi:10.1137/0219076. 1, 2

work page doi:10.1137/0219076 1990
[17]

J. H. Lutz. Almost everywhere high nonuniform complexity.Journal of Computer and System Sciences, 44(2):220–258, 1992.doi:10.1016/0022-0000(92)90020-j. 2, 3

work page doi:10.1016/0022-0000(92)90020-j 1992
[18]

J. H. Lutz and E. Mayordomo. Twelve problems in resource-bounded measure. In G. P ˘aun, G. Rozenberg, and A. Salomaa, editors,Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83–101. World Scientific Publishing, 2001.doi:10.1142/9789812810403_0001. 5

work page doi:10.1142/9789812810403_0001 2001
[19]

Mayordomo

E. Mayordomo. Almost every set in exponential time is P-bi-immune.Theoretical Computer Science, 136(2):487–506, 1994.doi:10.1016/0304-3975(94)00023-c. 1

work page doi:10.1016/0304-3975(94)00023-c 1994
[20]

P. B. Miltersen, N. V . Vinodchandran, and O. Watanabe. Superpolynomial versus subexponential circuit size in the exponential hierarchy. InProceedings of the Fifth Annual International Computing and Combinatorics Conference, pages 210–220, 1999.doi:10.1007/3-540-48686-0\_21. 1

work page doi:10.1007/3-540-48686-0 1999
[21]

Symmetric alternation captures BPP.Comput

Alexander Russell and Ravi Sundaram. Symmetric alternation captures BPP.Comput. Complex., 7(2):152– 162, 1998.doi:10.1007/S000370050007. 1, 2 6

work page doi:10.1007/s000370050007 1998

[1] [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. 1

2010

[2] [2]

Aydinlioglu, D

B. Aydinlioglu, D. Gutfreund, J. M. Hitchcock, and A. Kawachi. Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds.Computational Complexity, 20(2):329–366, 2011.doi:10.1007/s00037-011-0010-8

work page doi:10.1007/s00037-011-0010-8 2011

[3] [3]

Nonrelativizing separations

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing separations. InProceedings of the 13th Annual IEEE Conference on Computational Complexity, pages 8–12. IEEE Computer Society, 1998. doi:10.1109/CCC.1998.694585. 1

work page doi:10.1109/ccc.1998.694585 1998

[4] [4]

Procedia CIRP72(March), 159–164 (2018) https://doi.org/10.1016/j

Jin-yi Cai.S p 2 ⊆ZPP NP.Journal of Computer and System Sciences, 73(1):25–35, 2007.doi:10.1016/J. JCSS.2003.07.015. 2, 4

work page doi:10.1016/j 2007

[5] [5]

More on BPP and the polynomial-time hierarchy.Information Processing Letters, 57(5):237–241, 1996.doi:10.1016/0020-0190(96)00016-6

Ran Canetti. More on BPP and the polynomial-time hierarchy.Information Processing Letters, 57(5):237–241, 1996.doi:10.1016/0020-0190(96)00016-6. 1, 2

work page doi:10.1016/0020-0190(96)00016-6 1996

[6] [6]

InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing(Vancouver, BC, Canada)(STOC 2024).AssociationforComputingMachinery,NewYork,NY,USA,1816–1819

Lijie Chen, Shuichi Hirahara, and Hanlin Ren. Symmetric exponential time requires near-maximum cir- cuit size. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1990–1999, New York, NY , USA, 2024. Association for Computing Machinery.doi:10.1145/3618260. 3649624. 1, 3, 4

work page doi:10.1145/3618260 2024

[7] [7]

Reviewing bounds on the circuit size of the hardest functions.Information Processing Letters, 95(2):354–357, 2005.doi:10.1016/j.ipl.2005.03.009

Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions.Information Processing Letters, 95(2):354–357, 2005.doi:10.1016/j.ipl.2005.03.009. 3

work page doi:10.1016/j.ipl.2005.03.009 2005

[8] [8]

J. M. Hitchcock, A. Sekoni, and H. Shafei. Counting martingales for measure and dimension in complexity classes. InProceedings of the 40th Computational Complexity Conference (CCC 2025), volume 339 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:35, 2025.doi:10.4230/LIPIcs.CCC. 2025.20. 3

work page doi:10.4230/lipics.ccc 2025

[9] [9]

J. M. Hitchcock and N. V . Vinodchandran. Dimension, entropy rates, and compression.Journal of Computer and System Sciences, 72(4):760–782, 2006.doi:10.1016/j.jcss.2005.10.002. 1

work page doi:10.1016/j.jcss.2005.10.002 2006

[10] [10]

R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets.Information and Control, 55(1- 3):40–56, 1982.doi:10.1016/s0019-9958(82)90382-5. 1, 4

work page doi:10.1016/s0019-9958(82)90382-5 1982

[11] [11]

Klivans and D

A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses.SIAM Journal on Computing, 31(5):1501–1526, 2002.doi:10.1137/ s0097539700389652. 4 5

2002

[12] [12]

The hardest explicit construction

Oliver Korten. The hardest explicit construction. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 433–444. IEEE, 2022.doi:10.1109/FOCS52979.2021.00051. 1, 3

work page doi:10.1109/focs52979.2021.00051 2022

[13] [13]

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 Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 2000–2007, New York, NY , USA, 2024. Association for Computing Machinery.doi:10.1145/3618260.3649615. 1, 3

work page doi:10.1145/3618260.3649615 2024

[14] [14]

J. H. Lutz. Resource-bounded Baire category and small circuits in exponential space. InProceedings of the Second Structure in Complexity Theory Conference, pages 81–91. IEEE Computer Society Press, 1987. doi:10.1109/psct.1987.10319257. 1, 2, 4

work page doi:10.1109/psct.1987.10319257 1987

[15] [15]

J. H. Lutz.Resource-Bounded Category and Measure in Exponential Complexity Classes. PhD thesis, Califor- nia Institute of Technology, 1987.doi:10.7907/qny92-v6h14

work page doi:10.7907/qny92-v6h14 1987

[16] [16]

J. H. Lutz. Category and measure in complexity classes.SIAM Journal on Computing, 19(6):1100–1131, 1990. doi:10.1137/0219076. 1, 2

work page doi:10.1137/0219076 1990

[17] [17]

J. H. Lutz. Almost everywhere high nonuniform complexity.Journal of Computer and System Sciences, 44(2):220–258, 1992.doi:10.1016/0022-0000(92)90020-j. 2, 3

work page doi:10.1016/0022-0000(92)90020-j 1992

[18] [18]

J. H. Lutz and E. Mayordomo. Twelve problems in resource-bounded measure. In G. P ˘aun, G. Rozenberg, and A. Salomaa, editors,Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83–101. World Scientific Publishing, 2001.doi:10.1142/9789812810403_0001. 5

work page doi:10.1142/9789812810403_0001 2001

[19] [19]

Mayordomo

E. Mayordomo. Almost every set in exponential time is P-bi-immune.Theoretical Computer Science, 136(2):487–506, 1994.doi:10.1016/0304-3975(94)00023-c. 1

work page doi:10.1016/0304-3975(94)00023-c 1994

[20] [20]

P. B. Miltersen, N. V . Vinodchandran, and O. Watanabe. Superpolynomial versus subexponential circuit size in the exponential hierarchy. InProceedings of the Fifth Annual International Computing and Combinatorics Conference, pages 210–220, 1999.doi:10.1007/3-540-48686-0\_21. 1

work page doi:10.1007/3-540-48686-0 1999

[21] [21]

Symmetric alternation captures BPP.Comput

Alexander Russell and Ravi Sundaram. Symmetric alternation captures BPP.Comput. Complex., 7(2):152– 162, 1998.doi:10.1007/S000370050007. 1, 2 6

work page doi:10.1007/s000370050007 1998