Optimal Lower Bounds for Symmetric Modular Circuits

Benedikt Pago

arxiv: 2604.04760 · v1 · submitted 2026-04-06 · 💻 cs.CC · cs.LO

Optimal Lower Bounds for Symmetric Modular Circuits

Benedikt Pago This is my paper

Pith reviewed 2026-05-10 19:06 UTC · model grok-4.3

classification 💻 cs.CC cs.LO

keywords symmetric circuitsmodular circuitslower boundsBoolean ANDcircuit complexityMOD gatesdepth-2 circuits

0 comments

The pith

Symmetric modular circuits computing the n-ary AND require subexponential size at any depth.

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

The paper establishes subexponential size lower bounds for modular circuits that remain unchanged under any reordering of their n input gates when they compute the AND of n bits. The bounds hold for circuits of arbitrary depth and any fixed modulus m. Because the lower bounds exactly match a known depth-2 upper bound construction, they imply that increasing depth brings no further size reduction under this symmetry constraint. The result is extended to circuits whose symmetry is relaxed to a nested block structure on the inputs, where matching lower bounds are also obtained.

Core claim

For any modulus m, any depth, and circuits that are syntactically symmetric under all permutations of the n inputs, the size needed to compute the n-ary Boolean AND is subexponential in n. This lower bound is tight, matching a depth-2 construction, so deeper circuits do not yield smaller sizes. Similar tight bounds hold when symmetry is relaxed to a nested block structure on the inputs.

What carries the argument

Syntactic symmetry under all permutations of the n input gates, which requires that the circuit wiring and gate types stay identical regardless of how the inputs are reordered.

Load-bearing premise

The circuits must be syntactically symmetric under all permutations of their n input gates.

What would settle it

A permutation-symmetric MOD_m circuit of size smaller than the stated subexponential bound that still computes the n-ary AND on infinitely many n would refute the lower bound.

read the original abstract

A notorious open question in circuit complexity is whether Boolean operations of arbitrary arity can efficiently be expressed using modular counting gates only. H{\aa}stad's celebrated switching lemma yields exponential lower bounds for the dual problem - realising modular arithmetic with Boolean gates - but, a similar lower bound for modular circuits computing the Boolean AND function has remained elusive for almost 30 years. We solve this problem for the restricted model of symmetric circuits: We consider MOD$_m$-circuits of arbitrary depth, and for an arbitrary modulus $m \in \mathbb{N}$, and obtain subexponential lower bounds for computing the $n$-ary Boolean AND function, under the assumption that the circuits are syntactically symmetric under all permutations of their $n$ input gates. This lower bound is matched precisely by a construction due to (Idziak, Kawa{\l}ek, Krzaczkowski, LICS'22), leading to the surprising conclusion that the optimal symmetric circuit size is already achieved with depth $2$. Motivated by another construction from (LICS'22), which achieves smaller size at the cost of greater depth, we also prove tight size lower bounds for circuits with a more liberal notion of symmetry characterised by a nested block structure on the input variables.

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 paper settles the symmetric case for modular circuit lower bounds on AND with a tight match to the known depth-2 construction.

read the letter

This paper gives subexponential lower bounds for symmetric modular circuits computing AND and matches them exactly to a known depth-2 upper bound. That is the core advance. It takes the symmetry assumption seriously and uses it to count how many gates can actually contribute to the output. Because the circuit must look the same after any permutation of inputs, most gates end up redundant when the function is AND. This leads to the size lower bound. The fact that it hits the upper bound from Idziak et al. means the construction is optimal within the symmetric model. The work does well by handling both the full symmetry and the nested block version from the same earlier paper. It avoids overclaiming by sticking to the restricted model where the symmetry lets the argument go through. The soft spots are limited. The main one is that full symmetry is quite strong, so this does not resolve the general case of modular circuits for AND. The proof depends on the syntactic definition of symmetry via the circuit graph being invariant, and the details of the counting step for arbitrary m would be worth verifying in the full text. There are no invented parameters or circular reductions apparent. This is aimed at people in circuit complexity who care about lower bounds for counting gates. It is the kind of paper that moves a specific open question forward with a clean answer. I would bring it to a reading group to dissect the symmetry reduction. It deserves a serious referee because the claim is sharp and the model is standard. Recommendation: send it out for review rather than desk reject.

Referee Report

0 major / 4 minor

Summary. The paper proves subexponential lower bounds on the size of syntactically symmetric MOD_m circuits (arbitrary depth, fixed m) computing the n-ary Boolean AND function. The bounds are shown to match exactly the size of the depth-2 construction of Idziak et al. (LICS'22), implying that depth 2 is optimal for symmetric circuits. A second result gives tight lower bounds under a weaker nested-block symmetry condition motivated by another LICS'22 construction.

Significance. If the counting argument holds, the result is significant: it resolves the symmetric case of a 30-year open question on modular-circuit lower bounds for AND, supplies matching upper and lower bounds (including the leading term), and demonstrates that additional depth cannot help under syntactic symmetry. The explicit matching with a known construction and the extension to nested blocks strengthen the contribution.

minor comments (4)

§2 (Definitions): the formal definition of 'syntactic symmetry' via the action of S_n on the circuit graph is clear, but the text should explicitly state whether the output gate is fixed or also permuted; this affects the counting argument in §4.
§4.2 (Counting argument): the transition from the symmetry assumption to the redundancy of many gates for AND is sketched at a high level; adding a short lemma that isolates the precise number of distinct gate types would improve readability without changing the proof.
Theorem 1.1 and the matching construction: the paper correctly notes that the lower bound is asymptotically tight, but should include a one-sentence reminder of the exact leading term from Idziak et al. to make the optimality claim self-contained.
§5 (Nested blocks): the reduction from general nested-block symmetry to the depth-2 case is only outlined; a diagram or small example would clarify how the block structure is preserved under the circuit operations.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. The assessment that the results resolve the symmetric case of the long-standing open question on modular-circuit lower bounds for AND, with matching upper and lower bounds including the leading term, is appreciated. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central lower-bound argument for symmetric MOD_m circuits computing n-ary AND proceeds from an explicit syntactic symmetry assumption (invariance of the circuit graph under S_n action on inputs) via a counting argument that identifies redundant gates. This is a direct combinatorial proof using standard circuit definitions and does not reduce to fitted parameters, self-definitions, or self-citations. The cited depth-2 construction from Idziak et al. (LICS'22) is an external upper bound used only for tightness comparison, not as a load-bearing premise in the lower-bound derivation. No equations or steps equate a claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the syntactic symmetry assumption (domain assumption) and standard definitions of MOD_m gates and circuit size; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Syntactic symmetry under all permutations of input gates defines the circuit class
Invoked to restrict the model for which lower bounds are proved
standard math Standard properties of modular counting gates and circuit depth/size measures
Background definitions from circuit complexity

pith-pipeline@v0.9.0 · 5511 in / 1221 out tokens · 51730 ms · 2026-05-10T19:06:17.291710+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

‘On Symmetric Circuits and Fixed-Point Logics’

Matthew Anderson and Anuj Dawar. ‘On Symmetric Circuits and Fixed-Point Logics’. In:Theory of Computing Systems60.3 (Apr. 2017), pp. 521–551.issn: 1432-4350, 1433- 0490.doi:10.1007/s00224-016-9692-2.url:http://link.springer.com/10.1007/ s00224-016-9692-2(visited on 16/04/2024). 20

work page doi:10.1007/s00224-016-9692-2.url:http://link.springer.com/10.1007/ 2017
[2]

Mix Barrington, Richard Beigel and Steven Rudich

David A. Mix Barrington, Richard Beigel and Steven Rudich. ‘Representing Boolean Functions as Polynomials Modulo Composite Numbers’. In:Computational Complexity 4 (1994), pp. 367–382.doi:10.1007/BF01263424.url:https://doi.org/10.1007/ BF01263424

work page doi:10.1007/bf01263424.url:https://doi.org/10.1007/ 1994
[3]

Mix Barrington, Howard Straubing and Denis Th´ erien

David A. Mix Barrington, Howard Straubing and Denis Th´ erien. ‘Non-Uniform Automata Over Groups’. In:Information and Computation89.2 (1990), pp. 109–132.doi:10.1016/ 0890-5401(90)90007-5.url:https://doi.org/10.1016/0890-5401(90)90007-5

work page doi:10.1016/0890-5401(90)90007-5 1990
[4]

Agostinelli, et al., Nuclear Instruments and Meth- ods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 506(3), 250 (2003)

Andreas Blass, Yuri Gurevich and Saharon Shelah. ‘Choiceless polynomial time’. In: Annals of Pure and Applied Logic100.1-3 (1999), pp. 141–187.doi:10.1016/S0168- 0072(99)00005-6

work page doi:10.1016/s0168- 1999
[5]

‘Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations’

Joshua Brakensiek, Sivakanth Gopi and Venkatesan Guruswami. ‘Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations’. In:SIAM Journal on Computing51.3 (2022), pp. 577–626

work page 2022
[6]

Ryan Williams

Brynmor Chapman and R. Ryan Williams. ‘Smaller ACC 0 Circuits for Symmetric Func- tions’. In:13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Vol. 215. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 38:1–38:19. doi:10.4230/LIPICS.ITCS.2022.38.url:https://doi.org/10.4230/LIPIcs.ITCS. 2022.38

work page doi:10.4230/lipics.itcs.2022.38.url:https://doi.org/10.4230/lipics.itcs 2022
[7]

‘Lower bounds for circuits with MOD m gates’

Arkadev Chattopadhyay et al. ‘Lower bounds for circuits with MOD m gates’. In:47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). 2006, pp. 709– 718.doi:10.1109/FOCS.2006.46

work page doi:10.1109/focs.2006.46 2006
[8]

Anuj Dawar, Benedikt Pago and Tim Seppelt.Symmetric Algebraic Circuits and Homo- morphism Polynomials. 2025. arXiv:2502.06740 [cs.CC].url:https://arxiv.org/ abs/2502.06740

work page arXiv 2025
[9]

‘Symmetric Algebraic Circuits and Homo- morphism Polynomials’

Anuj Dawar, Benedikt Pago and Tim Seppelt. ‘Symmetric Algebraic Circuits and Homo- morphism Polynomials’. In:17th Innovations in Theoretical Computer Science Conference (ITCS 2026). 2026.doi:10.4230/LIPIcs.ITCS.2026.46

work page doi:10.4230/lipics.itcs.2026.46 2026
[10]

‘Symmetric Arithmetic Circuits’

Anuj Dawar and Gregory Wilsenach. ‘Symmetric Arithmetic Circuits’. In:47th Interna- tional Colloquium on Automata, Languages, and Programming, ICALP 2020. Vol. 168. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2020, 36:1–36:18.doi:10. 4230/LIPIcs.ICALP.2020.36.url:https://doi.org/10.4230/LIPIcs.ICALP.2020. 36

work page doi:10.4230/lipics.icalp.2020 2020
[11]

‘Lower Bounds for Symmetric Circuits for the De- terminant’

Anuj Dawar and Gregory Wilsenach. ‘Lower Bounds for Symmetric Circuits for the De- terminant’. In:13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA. Ed. by Mark Braverman. Vol. 215. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022, 52:1–52:22.doi:10. 4230/LIPICS.ITCS.2...

work page doi:10.4230/lipics.itcs.2022.52 2022
[12]

19th Jan

Anuj Dawar and Gregory Wilsenach.Symmetric Arithmetic Circuits. 19th Jan. 2024. arXiv:2002.06451[cs].url:http://arxiv.org/abs/2002.06451(visited on 05/04/2024)

work page arXiv 2024
[13]

‘Matching Vector Codes’

Zeev Dvir, Parikshit Gopalan and Sergey Yekhanin. ‘Matching Vector Codes’. In:SIAM Journal on Computing40.4 (2011), pp. 1154–1178

work page 2011
[14]

‘2-Server PIR with Sub-Polynomial Communication’

Zeev Dvir and Sivakanth Gopi. ‘2-Server PIR with Sub-Polynomial Communication’. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. 2015, pp. 577–584

work page 2015
[15]

2026.doi:10

Prateek Dwivedi, Benedikt Pago and Tim Seppelt.Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials. 2026.doi:10 . 48550 / arXiv . 2601 . 09343. 21

work page 2026
[16]

‘3-Query Locally Decodable Codes of Subexponential Length’

Klim Efremenko. ‘3-Query Locally Decodable Codes of Subexponential Length’. In:SIAM J. Comput.41.6 (2012), pp. 1694–1703.doi:10.1137/090772721.url:https://doi. org/10.1137/090772721

work page doi:10.1137/090772721.url:https://doi 2012
[17]

Zuiddam, The asymptotic spectrum of graphs and the Shannon ca- pacity, Combinatorica 39 (5) (2019) 1173–1184.doi:10.1007/s00493- 019-3992-5

Parikshit Gopalan. ‘Constructing Ramsey graphs from Boolean function representations’. In:Comb.34.2 (2014), pp. 173–206.doi:10.1007/S00493- 014- 2367- 1.url:https: //doi.org/10.1007/s00493-014-2367-1

work page doi:10.1007/s00493- 2014
[18]

‘Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs’

Vince Grolmusz. ‘Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs’. In:Combinatorica20.1 (2000), pp. 71–86

work page 2000
[19]

‘A Degree-Decreasing Lemma for (MOD p-MODm) Circuits’

Vince Grolmusz. ‘A Degree-Decreasing Lemma for (MOD p-MODm) Circuits’. In:Discrete Mathematics and Theoretical Computer Science4.2 (2001), pp. 247–254.doi:10.46298/ dmtcs.289

work page 2001
[20]

‘Lower Bounds for (MOD p-MODm) Circuits’

Vince Grolmusz and G´ abor Tardos. ‘Lower Bounds for (MOD p-MODm) Circuits’. In: SIAM Journal on Computing29.4 (2000), pp. 1209–1222.doi:10.1137/S0097539798340850. url:https://doi.org/10.1137/S0097539798340850

work page doi:10.1137/s0097539798340850 2000
[21]

‘Computational limitations for small depth circuits’

Johan H˚ astad. ‘Computational limitations for small depth circuits’. PhD thesis. Mas- sachusetts Institute of Technology, 1986

work page 1986
[22]

‘Symmetric Formulas for Products of Permutations’

William He and Benjamin Rossman. ‘Symmetric Formulas for Products of Permutations’. In:14th Innovations in Theoretical Computer Science Conference, ITCS. Vol. 251. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2023, 68:1–68:23.doi:10 . 4230 / LIPICS.ITCS.2023.68.url:https://doi.org/10.4230/LIPIcs.ITCS.2023.68

work page doi:10.4230/lipics.itcs.2023.68 2023
[23]

Idziak, Piotr Kawa lek and Jacek Krzaczkowski

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Intermediate Problems in Mod- ular Circuits Satisfiability’. In:Proceedings of LICS’20: 35th Annual ACM/IEEE Sym- posium on Logic in Computer Science. Saarbr¨ ucken, Germany, 2020, pp. 578–590.isbn: 9781450371049.doi:10.1145/3373718.3394780.url:https://doi.org/10.1145/ 3373718.3394780

work page doi:10.1145/3373718.3394780.url:https://doi.org/10.1145/ 2020
[24]

LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Complexity of Modular Cir- cuits’. In:Proceedings of LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, 2022, 32:1–32:11.doi:10.1145/3531130.3533350.url:https: //doi.org/10.1145/3531130.3533350

work page doi:10.1145/3531130.3533350.url:https: 2022
[25]

Idziak, Piotr Kawa lek and Jacek Krzaczkowski

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Nonuniform Deterministic Fi- nite Automata over Finite Algebraic Structures’. In:52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Vol. 334. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Info...

work page 2025
[26]

Idziak et al

Pawe l M. Idziak et al. ‘Satisfiability Problems for Finite Groups’. In:49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 127:1–127:20.isbn: 978-3- 95977-235-8.doi:10.4230/LIPIcs.ICALP.2022.127.url:https://drops.dagstuhl. de/opus/volltexte/2022/16468

work page doi:10.4230/lipics.icalp.2022.127.url:https://drops.dagstuhl 2022
[27]

Efficiently Testing Simon’s Congruence

Piotr Kawa lek and Armin Weiß. ‘Violating Constant Degree Hypothesis Requires Break- ing Symmetry’. In:42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Ed. by Olaf Beyersdorff et al. Vol. 327. Leibniz International Pro- ceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Inform...

work page doi:10.4230/lipics.stacs 2025
[28]

Alexandre Laugier and Manjil Saikia.Periodic Sequences modulom. 2015. arXiv:1209. 2371 [math.NT].url:https://arxiv.org/abs/1209.2371

work page arXiv 2015
[29]

‘Algebraic methods in the theory of lower bounds for Boolean circuit complexity’

Roman Smolensky. ‘Algebraic methods in the theory of lower bounds for Boolean circuit complexity’. In:Proceedings of the 19th Annual ACM Symposium on Theory of Comput- ing, 1987. ACM, 1987, pp. 77–82

work page 1987
[30]

‘A note on MOD p-MODm circuits’

Howard Straubing and Denis Th´ erien. ‘A note on MOD p-MODm circuits’. In:Theory of Computing Systems39.5 (2006), pp. 699–706. 23 A Details on symmetry groups and circuits We first give a detailed proof of the claim that symmetric MODm-circuits can always be assumed to be rigid. Lemma A.1(Rigidification).LetΓ≤Sym n. IfCis aΓ-symmetric circuitMOD m-circuit...

work page 2006

[1] [1]

‘On Symmetric Circuits and Fixed-Point Logics’

Matthew Anderson and Anuj Dawar. ‘On Symmetric Circuits and Fixed-Point Logics’. In:Theory of Computing Systems60.3 (Apr. 2017), pp. 521–551.issn: 1432-4350, 1433- 0490.doi:10.1007/s00224-016-9692-2.url:http://link.springer.com/10.1007/ s00224-016-9692-2(visited on 16/04/2024). 20

work page doi:10.1007/s00224-016-9692-2.url:http://link.springer.com/10.1007/ 2017

[2] [2]

Mix Barrington, Richard Beigel and Steven Rudich

David A. Mix Barrington, Richard Beigel and Steven Rudich. ‘Representing Boolean Functions as Polynomials Modulo Composite Numbers’. In:Computational Complexity 4 (1994), pp. 367–382.doi:10.1007/BF01263424.url:https://doi.org/10.1007/ BF01263424

work page doi:10.1007/bf01263424.url:https://doi.org/10.1007/ 1994

[3] [3]

Mix Barrington, Howard Straubing and Denis Th´ erien

David A. Mix Barrington, Howard Straubing and Denis Th´ erien. ‘Non-Uniform Automata Over Groups’. In:Information and Computation89.2 (1990), pp. 109–132.doi:10.1016/ 0890-5401(90)90007-5.url:https://doi.org/10.1016/0890-5401(90)90007-5

work page doi:10.1016/0890-5401(90)90007-5 1990

[4] [4]

Agostinelli, et al., Nuclear Instruments and Meth- ods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 506(3), 250 (2003)

Andreas Blass, Yuri Gurevich and Saharon Shelah. ‘Choiceless polynomial time’. In: Annals of Pure and Applied Logic100.1-3 (1999), pp. 141–187.doi:10.1016/S0168- 0072(99)00005-6

work page doi:10.1016/s0168- 1999

[5] [5]

‘Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations’

Joshua Brakensiek, Sivakanth Gopi and Venkatesan Guruswami. ‘Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations’. In:SIAM Journal on Computing51.3 (2022), pp. 577–626

work page 2022

[6] [6]

Ryan Williams

Brynmor Chapman and R. Ryan Williams. ‘Smaller ACC 0 Circuits for Symmetric Func- tions’. In:13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Vol. 215. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 38:1–38:19. doi:10.4230/LIPICS.ITCS.2022.38.url:https://doi.org/10.4230/LIPIcs.ITCS. 2022.38

work page doi:10.4230/lipics.itcs.2022.38.url:https://doi.org/10.4230/lipics.itcs 2022

[7] [7]

‘Lower bounds for circuits with MOD m gates’

Arkadev Chattopadhyay et al. ‘Lower bounds for circuits with MOD m gates’. In:47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). 2006, pp. 709– 718.doi:10.1109/FOCS.2006.46

work page doi:10.1109/focs.2006.46 2006

[8] [8]

Anuj Dawar, Benedikt Pago and Tim Seppelt.Symmetric Algebraic Circuits and Homo- morphism Polynomials. 2025. arXiv:2502.06740 [cs.CC].url:https://arxiv.org/ abs/2502.06740

work page arXiv 2025

[9] [9]

‘Symmetric Algebraic Circuits and Homo- morphism Polynomials’

Anuj Dawar, Benedikt Pago and Tim Seppelt. ‘Symmetric Algebraic Circuits and Homo- morphism Polynomials’. In:17th Innovations in Theoretical Computer Science Conference (ITCS 2026). 2026.doi:10.4230/LIPIcs.ITCS.2026.46

work page doi:10.4230/lipics.itcs.2026.46 2026

[10] [10]

‘Symmetric Arithmetic Circuits’

Anuj Dawar and Gregory Wilsenach. ‘Symmetric Arithmetic Circuits’. In:47th Interna- tional Colloquium on Automata, Languages, and Programming, ICALP 2020. Vol. 168. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2020, 36:1–36:18.doi:10. 4230/LIPIcs.ICALP.2020.36.url:https://doi.org/10.4230/LIPIcs.ICALP.2020. 36

work page doi:10.4230/lipics.icalp.2020 2020

[11] [11]

‘Lower Bounds for Symmetric Circuits for the De- terminant’

Anuj Dawar and Gregory Wilsenach. ‘Lower Bounds for Symmetric Circuits for the De- terminant’. In:13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA. Ed. by Mark Braverman. Vol. 215. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022, 52:1–52:22.doi:10. 4230/LIPICS.ITCS.2...

work page doi:10.4230/lipics.itcs.2022.52 2022

[12] [12]

19th Jan

Anuj Dawar and Gregory Wilsenach.Symmetric Arithmetic Circuits. 19th Jan. 2024. arXiv:2002.06451[cs].url:http://arxiv.org/abs/2002.06451(visited on 05/04/2024)

work page arXiv 2024

[13] [13]

‘Matching Vector Codes’

Zeev Dvir, Parikshit Gopalan and Sergey Yekhanin. ‘Matching Vector Codes’. In:SIAM Journal on Computing40.4 (2011), pp. 1154–1178

work page 2011

[14] [14]

‘2-Server PIR with Sub-Polynomial Communication’

Zeev Dvir and Sivakanth Gopi. ‘2-Server PIR with Sub-Polynomial Communication’. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. 2015, pp. 577–584

work page 2015

[15] [15]

2026.doi:10

Prateek Dwivedi, Benedikt Pago and Tim Seppelt.Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials. 2026.doi:10 . 48550 / arXiv . 2601 . 09343. 21

work page 2026

[16] [16]

‘3-Query Locally Decodable Codes of Subexponential Length’

Klim Efremenko. ‘3-Query Locally Decodable Codes of Subexponential Length’. In:SIAM J. Comput.41.6 (2012), pp. 1694–1703.doi:10.1137/090772721.url:https://doi. org/10.1137/090772721

work page doi:10.1137/090772721.url:https://doi 2012

[17] [17]

Zuiddam, The asymptotic spectrum of graphs and the Shannon ca- pacity, Combinatorica 39 (5) (2019) 1173–1184.doi:10.1007/s00493- 019-3992-5

Parikshit Gopalan. ‘Constructing Ramsey graphs from Boolean function representations’. In:Comb.34.2 (2014), pp. 173–206.doi:10.1007/S00493- 014- 2367- 1.url:https: //doi.org/10.1007/s00493-014-2367-1

work page doi:10.1007/s00493- 2014

[18] [18]

‘Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs’

Vince Grolmusz. ‘Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs’. In:Combinatorica20.1 (2000), pp. 71–86

work page 2000

[19] [19]

‘A Degree-Decreasing Lemma for (MOD p-MODm) Circuits’

Vince Grolmusz. ‘A Degree-Decreasing Lemma for (MOD p-MODm) Circuits’. In:Discrete Mathematics and Theoretical Computer Science4.2 (2001), pp. 247–254.doi:10.46298/ dmtcs.289

work page 2001

[20] [20]

‘Lower Bounds for (MOD p-MODm) Circuits’

Vince Grolmusz and G´ abor Tardos. ‘Lower Bounds for (MOD p-MODm) Circuits’. In: SIAM Journal on Computing29.4 (2000), pp. 1209–1222.doi:10.1137/S0097539798340850. url:https://doi.org/10.1137/S0097539798340850

work page doi:10.1137/s0097539798340850 2000

[21] [21]

‘Computational limitations for small depth circuits’

Johan H˚ astad. ‘Computational limitations for small depth circuits’. PhD thesis. Mas- sachusetts Institute of Technology, 1986

work page 1986

[22] [22]

‘Symmetric Formulas for Products of Permutations’

William He and Benjamin Rossman. ‘Symmetric Formulas for Products of Permutations’. In:14th Innovations in Theoretical Computer Science Conference, ITCS. Vol. 251. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2023, 68:1–68:23.doi:10 . 4230 / LIPICS.ITCS.2023.68.url:https://doi.org/10.4230/LIPIcs.ITCS.2023.68

work page doi:10.4230/lipics.itcs.2023.68 2023

[23] [23]

Idziak, Piotr Kawa lek and Jacek Krzaczkowski

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Intermediate Problems in Mod- ular Circuits Satisfiability’. In:Proceedings of LICS’20: 35th Annual ACM/IEEE Sym- posium on Logic in Computer Science. Saarbr¨ ucken, Germany, 2020, pp. 578–590.isbn: 9781450371049.doi:10.1145/3373718.3394780.url:https://doi.org/10.1145/ 3373718.3394780

work page doi:10.1145/3373718.3394780.url:https://doi.org/10.1145/ 2020

[24] [24]

LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Complexity of Modular Cir- cuits’. In:Proceedings of LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, 2022, 32:1–32:11.doi:10.1145/3531130.3533350.url:https: //doi.org/10.1145/3531130.3533350

work page doi:10.1145/3531130.3533350.url:https: 2022

[25] [25]

Idziak, Piotr Kawa lek and Jacek Krzaczkowski

Pawe l M. Idziak, Piotr Kawa lek and Jacek Krzaczkowski. ‘Nonuniform Deterministic Fi- nite Automata over Finite Algebraic Structures’. In:52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Vol. 334. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Info...

work page 2025

[26] [26]

Idziak et al

Pawe l M. Idziak et al. ‘Satisfiability Problems for Finite Groups’. In:49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2022, 127:1–127:20.isbn: 978-3- 95977-235-8.doi:10.4230/LIPIcs.ICALP.2022.127.url:https://drops.dagstuhl. de/opus/volltexte/2022/16468

work page doi:10.4230/lipics.icalp.2022.127.url:https://drops.dagstuhl 2022

[27] [27]

Efficiently Testing Simon’s Congruence

Piotr Kawa lek and Armin Weiß. ‘Violating Constant Degree Hypothesis Requires Break- ing Symmetry’. In:42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Ed. by Olaf Beyersdorff et al. Vol. 327. Leibniz International Pro- ceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Inform...

work page doi:10.4230/lipics.stacs 2025

[28] [28]

Alexandre Laugier and Manjil Saikia.Periodic Sequences modulom. 2015. arXiv:1209. 2371 [math.NT].url:https://arxiv.org/abs/1209.2371

work page arXiv 2015

[29] [29]

‘Algebraic methods in the theory of lower bounds for Boolean circuit complexity’

Roman Smolensky. ‘Algebraic methods in the theory of lower bounds for Boolean circuit complexity’. In:Proceedings of the 19th Annual ACM Symposium on Theory of Comput- ing, 1987. ACM, 1987, pp. 77–82

work page 1987

[30] [30]

‘A note on MOD p-MODm circuits’

Howard Straubing and Denis Th´ erien. ‘A note on MOD p-MODm circuits’. In:Theory of Computing Systems39.5 (2006), pp. 699–706. 23 A Details on symmetry groups and circuits We first give a detailed proof of the claim that symmetric MODm-circuits can always be assumed to be rigid. Lemma A.1(Rigidification).LetΓ≤Sym n. IfCis aΓ-symmetric circuitMOD m-circuit...

work page 2006