betaFeedback

WorksComputer Science

Depth Hierarchies for Symmetric Algebraic Circuits

Abstract

Algebraic complexity studies the cost of computing families of polynomials by algebraic circuits, with the central goal of proving super-polynomial circuit lower bounds and separations between different models of algebraic computation. Since such lower bounds remain elusive for general circuits, a common strategy is to focus on restricted models. A recent line of work (ICALP 2020, ITCS & STOC 2026) introduces and studies symmetry as a syntactic circuit restriction, showing exponential symmetric lower bounds for the permanent, as well as separations between symmetric analogues of algebraic formulas (VF\mathsf{VF}), skew circuits (VS\mathsf{VS}), and circuits (VP\mathsf{VP}). We investigate the role of depth as a complexity parameter in symmetric circuits. For every fixed Δ≥1Δ\geq 1, we exhibit a family of polynomials computable by symmetric circuits of polynomial size and depth 2Δ+32Δ+3, but requiring size nΩ(log⁡n)n^{Ω(\log n)} at depth ΔΔ. We also define symmetric versions of the bounded-depth algebraic complexity classes VACk\mathsf{VAC}^k, for all k∈Nk \in \mathbb{N}, that we call symVACk\mathsf{symVAC}^k, and establish two strict hierarchies: Firstly, a hierarchy within symVAC0\mathsf{symVAC}^0, and secondly, a hierarchy of the form symVACk⊊symVACk+1\mathsf{symVAC}^k \subsetneq \mathsf{symVAC}^{k+1} for all kk. The latter shows that symmetric circuits of depth (log⁡n)k+1(\log n)^{k+1} are strictly more powerful than depth-(log⁡n)k(\log n)^k circuits. Moreover, we place the bounded-depth classes within the landscape of symmetric algebraic complexity developed by Dwivedi, Pago and Seppelt (STOC 2026). We complement this picture by introducing symVNP\mathsf{symVNP}, a symmetric analogue of VNP\mathsf{VNP}, and establishing symVNP\mathsf{symVNP}-completeness of the permanent under symmetric projections.

Contents

    1. Introduction 1 1.1. Results 2 1.2. Techniques 5 1.3. Future work 6

    1. Preliminaries 7 2.1. Circuits and polynomial families 7 2.2. Matrix symmetry and orbit size 7 2.3. Rigid circuits, supports, and support depth 7 2.4. Homomorphism polynomials and graph parameters 8 2.5. Symmetric algebraic complexity classes 9

    1. Symmetric constant-depth hierarchy 9 3.1. Characterisations 10 3.2. Separation 11

    1. Symmetric depth reduction 11

    1. Symmetric polylogarithmic-depth hierarchy 12 5.1. Constant-depth reduction for formulas 13 5.2. Bounded pathwidth in logarithmic support depth 13 5.3. Separating symVAC1^{1} from symVP 14

    1. Symmetric algebraic branching programs 14

    1. Symmetric VNP 16 7.1. symVNP contains all matrix-symmetric polynomials 17 7.2. Hypercube sums of symmetric formulas 19 7.3. Completeness of the permanent under symmetric projections 19

  • Acknowledgements 21

  • References 22

  • A. Reduced circuits and supports 27

  • B. Material omitted in Section 3 28 B.1. Circuits for patterns of bounded forestwidth 28 B.2. Homomorphism polynomials from symmetric circuits 30 B.2.1. Labelled graphs 30 B.2.2. Eliminating many labels at once 32 B.2.3. Induction on the circuit 33 B.3. Combinatorics of bounded-depth tree decompositions 33 B.3.1. Richness 34 B.3.2. Oddomorphisms reflect richness 35 B.4. Non-uniform descriptive complexity monotonicity 36 B.4.1. CFI graphs for non-induced minors 36 B.4.2. Proof of Theorem 3.7 39

Introduction

Algebraic complexity theory studies families of polynomials in terms of the algebraic circuit size that is required to represent them. An algebraic circuit is a directed acyclic graph whose internal vertices correspond to addition and multiplication gates and whose input gates are labelled with variables or constants from a fixed underlying field. It computes a polynomial in the input variables in the natural way, and the circuit size is defined as the total number of gates and wires it contains. In 1979, Valiant postulated the conjecture that the permanent polynomial, i.e., the determinant without signs, does not admit polynomial-size algebraic circuits [56]. A central part of the algebraic complexity programme is thus to develop techniques for proving circuit size lower bounds. The common approach is to begin with restricted circuit models, where lower bounds are easier to establish. A substantial line of work has focussed on proving lower bounds for example on monotone or multilinear circuits and formulas [35]. Arguably, these results tell us more about the weakness of the restricted models than about the true complexity of the permanent: In fact, many of them, like the exponential lower bound for multilinear formulas computing the permanent [47], apply equally to the determinant, even though the determinant is known to admit polynomial-size circuits.

In recent years, a new circuit restriction has been investigated [19, 18 DPS26a, 21], in which determinant and permanent provably do exhibit a polynomial versus exponential complexity gap, in line with Valiant’s conjecture. This model is that of symmetric circuits. Not only has the separation between determinant and permanent [18] been established for this model, but also the separations of symmetric analogues of the major classes in algebraic complexity, that is, VF, VBP/ VS, and VP [21] (corresponding to algebraic formulas, branching programs or skew circuits, and general circuits, respectively). Briefly, the notion of symmetry means the following: Whenever a polynomial p∈K[X]p \in\mathbb{K}[X] is invariant under a permutation group Γ\Gamma acting on the variables XX, then it makes sense to require Γ\Gamma-symmetry also of a circuit CC that computes pp. A circuit CC is Γ\Gamma-symmetric if, for every permutation π∈Γ\pi\in\Gamma that acts on the input variables, there also exists a permutation σ\sigma of the gates of CC that is consistent with π\pi on the input gates, and preserves the wire structure of the circuit (that is, is an automorphism of CC). For a formal definition, see § 2.2. In this paper and in most of the works referenced above, the group Γ\Gamma is always Symn×Symn\mathrm{Sym}_n \times\mathrm{Sym}_n, and it acts via row and column permutations on variables Xn:={xij∣i,j∈[n]}X_n := \{x_{ij} \mid i,j \in[n]\} that are arranged in an n×nn \times n matrix. This notion is called matrix symmetry, and it applies to matrix polynomials such as the permanent and many other natural polynomials1 from algebraic complexity.

The recent lower bounds and separation results for symmetric circuits establish this model as an important and promising concept that merits further investigation. In this paper, we focus on the interplay of symmetry and depth in algebraic circuits. Bounded-depth circuit classes are a natural notion that has been studied extensively both in the algebraic and the Boolean setting. We prove depth hierarchies for symmetric circuits and place them in the existing symmetric algebraic circuit complexity landscape. A depth hierarchy is a statement along those lines: For every Δ∈N\Delta\in\mathbb{N}, there exist families of polynomials that are computable by depth-Δ\Delta circuits of polynomial size but require super-polynomial size to be computed by a circuit of depth <Δ< \Delta. Such depth hierarchy results were first shown for restricted circuit models, such as constant-depth multilinear formulas [49, 12], and recently for general constant-depth algebraic circuits in the breakthrough by Limaye, Srinivasan and Tavenas [39]. Other known results in this style are the separation between multilinear NC1\mathrm{NC}^{1} and NC2\mathrm{NC}^{2} circuits [48], and depth hierarchies of various strengths in the Boolean setting, that is, for AC0\mathrm{AC}^{0} circuits [54, 31, 32].

Results

Our main results establish depth hierarchies for symmetric algebraic circuits, both within the constant-depth regime between Δ\Delta and Δ+1\Delta+1, as well as between depths (log⁡n)k(\log n)^k and (log⁡n)k+1(\log n)^{k+1} for all constants kk. The former is a symmetric analogue of the depth hierarchy inside VAC0\mathrm{VAC}^{0}, which is the class of polynomials computable by constant-depth polynomial-size circuits, and the latter shows a hierarchy between symmetric analogues of the classes VACk\mathrm{VAC}^{k} and VACk+1\mathrm{VAC}^{k+1} for all kk.

These results are not implied by the hierarchies that are known in the non-symmetric setting, and are in some sense incomparable: While the symmetric model is syntactically restricted, its complexity measure is more lenient than for standard circuits. Namely, the natural size parameter of symmetric circuits is their orbit size, which is the number of gates in its largest orbit under the action of the symmetry group. Thus, a circuit can be considered efficient under symmetry aspects even when it contains a super-polynomial number of gates, as long as for each gate, there is at most a polynomial number of gates that are symmetric to it. A circuit with super-polynomial orbit size has in particular super-polynomial size, so lower bound results for symmetric circuits apply to the standard notion of size (i.e., total number of gates), too. Our depth hierarchy holds both with respect to the orbit size and standard circuit size measure.

Theorem 1.1. Fix any Δ≥1\Delta\ge1. There is a family (pn)n∈N(p_n)_{n\in\mathbb{N}} of matrix-symmetric polynomials such that

  1. Every matrix-symmetric circuit of depth ≤Δ\le\Delta computing pnp_n has size at least nΩ(log⁡2n)n^{\Omega(\log_2 n)}.

  2. There is a matrix-symmetric circuit of depth 2Δ+32\Delta+3 and size O(nΔ+2)O(n^{\Delta+2}) computing pnp_n.

Stated in terms of the notion of support depth, which is the semantically relevant depth parameter for symmetric circuits (see § 2.3), the separation is in fact between Δ\Delta and Δ+1\Delta+1, see Theorem 3.1 for the formal statement. This is similar to other depth hierarchy results where product depth, rather than depth, is the relevant measure. Moreover, support depth and depth agree up to a factor of 2 at polynomial orbit size, as we will see in Corollary 3.6.

Theorem 1.1 motivates introducing bounded-depth symmetric algebraic complexity classes and locating them in the symmetric algebraic complexity hierarchy

symVF⊊symVS⊊symVP\mathrm{symVF} \subsetneq\mathrm{symVS} \subsetneq\mathrm{symVP}

that was established in [21]. Using sophisticated machinery from finite model theory [27] and the theory of homomorphism indistinguishability [51], we place the bounded-depth classes in the existing picture, and unconditionally establish the separations depicted in Figure 1.

Figure 1. The classical landscape of algebraic complexity classes (left) and the symmetric landscape developed here (middle). Dotted lines connect symmetric classes to their classical counterparts (by identifying size with orbit size, depth with support depth). On the classical side, all classes consist of pp-families, that is, families of polynomials with polynomially bounded degree: VP and VNP by definition, VAC0\mathrm{VAC}^{0}, VF=VNC1\mathrm{VF}=\mathrm{VNC}^{1}, and VBP automatically, and VAC1\mathrm{VAC}^{1} and VNC are restricted to pp-families. Each symmetric class consists precisely of the linear combinations of homomorphism polynomials hom⁡F,n\operatorname{hom}_{F,n} for patterns FF satisfying the condition on the right, for a constant cc. Restricted to pp-families, symVP and symVAC1\mathrm{symVAC}^{1} are equal.

Definition 1.2. For Δ≥0\Delta\ge0, let symVACΔ0\mathrm{symVAC}^{0}_{\Delta} denote the class of families (pn)(p_n) of matrix-symmetric polynomials for which there is a constant cc such that, for all sufficiently large nn, the polynomial pnp_n is computed by a matrix-symmetric circuit of orbit size ≤nc\le n^c and support depth ≤Δ\le\Delta. Let symVAC0:=⋃Δ≥0symVACΔ0\mathrm{symVAC}^{0} := \bigcup_{\Delta\ge0}\mathrm{symVAC}^{0}_{\Delta}.

For k≥1k \ge1, let symVACk\mathrm{symVAC}^{k} denote the class of families (pn)(p_n) of matrix-symmetric polynomials for which there is a constant cc such that, for all sufficiently large nn, the polynomial pnp_n is computed by a matrix-symmetric circuit of orbit size ≤nc\le n^c and support depth ≤clog⁡kn\le c\log^{k} n. Let symVAC:=⋃k≥1symVACk\mathrm{symVAC} := \bigcup_{k\ge1}\mathrm{symVAC}^{k}.

Symmetric algebraic complexity classes and homomorphism polynomials. The classes symVF\mathrm{symVF}, symVS\mathrm{symVS}, and symVP\mathrm{symVP} comprise matrix-symmetric polynomials that are computable by matrix-symmetric formulas, skew circuits, and circuits of polynomial orbit size, respectively. The main technical contribution of [18, 21] was a characterisation of these syntactic circuit classes in terms of a graph-theoretic semantics: Each of these classes consists precisely of linear combinations of homomorphism polynomials of patterns of bounded treedepth, bounded pathwidth and bounded treewidth, respectively, cf. Theorem 2.9. A homomorphism polynomial

hom⁡F,n(X)=∑h:V(F)→[n]∏ab∈E(F)xh(a),h(b)\operatorname{hom}_{F,n}(X)=\sum_{h:V(F)\to[n]}\prod_{ab\in E(F)}x_{h(a),h(b)}

is parametrised by a pattern graph FF and the size nn of the target graph. Its variables can be instantiated with the adjacency matrix of an nn-vertex graph GG, and hom⁡F,n(G)\operatorname{hom}_{F,n}(G) evaluates to the number of homomorphisms from FF to GG. The separation of the symmetric algebraic complexity classes then follows from the separation of the graph distinguishing power of the corresponding classes of homomorphism polynomials.

The right column of Figure 1 describes the structural graph parameter of the homomorphism polynomials whose linear combinations capture the respective symmetric algebraic complexity class. For example, the correspondence between symVP\mathrm{symVP} and tw⁡(F)≤c\operatorname{tw}(F)\le c of [DPS26a] is to be read as follows: A family (pn)n∈N(p_n)_{n\in\mathbb{N}} is in symVP\mathrm{symVP} if and only if there is a fixed constant c∈Nc\in\mathbb{N} such that for every n∈Nn\in\mathbb{N}

pn(X)=∑F with tw⁡(F)≤cαF,n⋅hom⁡F,n(X),(1)p_n(X)=\sum_{F\ \mathrm{with}\ \operatorname{tw}(F)\le c}\alpha_{F,n}\cdot\operatorname{hom}_{F,n}(X), \tag*{(1)}

for some choice of coefficients αF,n∈K\alpha_{F,n}\in\mathbb{K}.

In Theorem 3.5, we prove a characterisation of the polynomials computed by matrix-symmetric circuits of a given orbit size and support depth. The graph parameter arising here is Δ\Delta-forestwidth fw⁡Δ\operatorname{fw}_{\Delta}, a graph parameter inspired by Δ\Delta-treewidth of Bhargav, Chen, Curticapean, and Dwivedi [Bha+25]: For Δ≥0\Delta\ge0, a graph FF has Δ\Delta-treewidth tw⁡Δ(F)≤k\operatorname{tw}_{\Delta}(F)\le k if it admits a tree decomposition (T,β)(T,\beta) of width ≤k\le k such that the decomposition tree is of depth at most Δ\Delta. For example, tw⁡0(F)=∣V(F)∣−1\operatorname{tw}_{0}(F)=|V(F)|-1, as Δ=0\Delta=0 forces the tree decomposition to consist of a single vertex, and tw⁡1(F)\operatorname{tw}_{1}(F) is closely related to the vertex-cover number of FF, see [Bha+25]. Bounded-depth tree decompositions are studied in finite model theory [1] and also arise as divide-and-conquer schemes for iterated matrix multiplication [39]. Δ\Delta-forestwidth differs from Δ\Delta-treewidth only in the additional technical requirement that the root bag be empty.

In order to describe the bounded-depth setting, our characterisation Theorem 3.5 needs to be more precise than previous results [21 DPS26a], which it fully subsumes. In particular, Theorem 3.5 does not only hold asymptotically but at every fixed host size nn, see § 3 for a discussion. This allows us to overcome the limitation of [21 DPS26a] to circuits of polynomial orbit size.

Comparing classical and symmetric hierarchies. The depth hierarchy within symVAC0\mathrm{symVAC}^{0} parallels the one within VAC0\mathrm{VAC}^{0}, though it follows from completely different arguments. As noted earlier, it is not just a special case of the result for VAC0\mathrm{VAC}^{0}, among other things because of the distinction of size versus orbit size. The separations between symVACk\mathrm{symVAC}^{k} and symVACk+1\mathrm{symVAC}^{k+1} have an essentially uninteresting analogue in the non-symmetric setting: Since the definition of VACk\mathrm{VAC}^{k} bounds total circuit size rather than orbit size, there is an upper bound of 2O(log⁡k+1n)2^{O(\log^{k+1}n)} on the degree of the polynomials that VACk\mathrm{VAC}^{k} can compute—therefore, VACk+1\mathrm{VAC}^{k+1} contains polynomials that are not in VACk\mathrm{VAC}^{k} simply because their degree is too large. The definition of symVACk\mathrm{symVAC}^{k}, however, puts no upper bound on the total circuit size, but rather on the orbit size. This does not entail an upper bound on the degree, so the separation between symVAC⁡k\operatorname{symVAC}^{k} and symVAC⁡k+1\operatorname{symVAC}^{k+1} is a genuine result, not an immediate consequence of the definition. It builds on quite sophisticated lower bounds on the iteration number of the Weisfeiler–Leman algorithm for graph isomorphism [27]. This iteration number translates into symmetric circuit depth via our homomorphism polynomial characterisation.

A new separation that we establish in the symmetric setting and which is not known to hold for non-symmetric circuits is symVBP⁡=symVS⁡⊊symVAC⁡1\operatorname{symVBP} = \operatorname{symVS} \subsetneq\operatorname{symVAC}^{1}. Even the inclusion, not just the separation, is surprising, given that no degree restrictions are imposed in these classes. For example, symVS contains the homomorphism polynomials of paths with 2n2^{n} vertices, whose natural representation in symVS has depth 22Ω(n)2^{2^{\Omega(n)}}. It is not at all straightforward to show that these polynomials are also in symVAC⁡1\operatorname{symVAC}^{1}, i.e., require only logarithmic depth. For pp-families, this follows from Theorem 4.1, but for families of higher degree, this requires substantially different techniques from invariant theory, as our graph-theoretic criterion alone does not yield this.

Symmetric VBP and VNP. As depicted in the figure, we also provide definitions of the symmetric classes symVNP and symVBP, for which no natural definitions were known so far. While symVS was defined in terms of symmetric skew circuits, symVBP comprises the families of polynomials computable by symmetric algebraic branching programs (ABPs) of polynomial orbit size. In the general non-symmetric setting, skew circuits and ABPs are polynomially equivalent. As we prove in Theorem 6.3, via the homomorphism polynomial characterisation, this carries over to the symmetric setting, so that we also have symVS = symVBP. In order to define the class symVNP, we place a natural symmetry condition on the definition of VNP in terms of hypercube sums over VP-polynomials, see Definition 7.1. This definition turns out to yield the correct symmetric analogue of VNP in the sense that it satisfies the following neat properties: Firstly, symVNP is equal to the class of all matrix-symmetric polynomials, see Theorem 7.3. Secondly, the permanent is complete for symVNP under symmetric projections (Theorem 7.7)—this is in analogy to the VNP-completeness of the permanent under not necessarily symmetric projections. Symmetric formulas are strictly weaker than symmetric circuits [21], Theorem A]. Nevertheless, Corollary 7.4 shows that their Boolean sums define the same class. Thus, as in classical VNP, restricting witnesses to formulas does not reduce expressive power.

Techniques

On a high level, the proof of Theorem 1.1 follows the strategy established in [21 DPS26a] for separating symmetric algebraic complexity classes. Its two ingredients are a characterisation of a symmetric algebraic complexity class in terms of homomorphism polynomials for patterns from some graph classes of restricted structure and a separation result asserting that a certain polynomial cannot be written as a linear combination of homomorphism polynomials for patterns from some graph class. However, the ideas in [21 DPS26a] are insufficient for Theorem 1.1 and need to be substantially refined.

Characterisations. The characterisations are insufficient as they only apply to circuits of polynomial orbit size. Our lower bounds require considering circuits of orbit size nΩ(log⁡n)n^{\Omega(\log n)} and thus a tighter analysis. Moreover, the most technical ingredient of [21 DPS26a], a lemma describing how support-changing gates affect the inductively constructed linear combination of homomorphism polynomials, needs to be replaced entirely. For details, see Appendix § 12.§ 2.

Separation. Even though every matrix-symmetric polynomial can be written as a linear combination of homomorphism polynomials, this linear combination is by no means unique; see [21 Example 3.1] and [13] for examples. Figure 1 also illustrates this: By Theorems 2.9, 3.5, and 5.2, it holds that symVBP⊆symVAC1\mathrm{symVBP} \subseteq\mathrm{symVAC}^{1}, i.e., every polynomial that can be written as a linear combination of homomorphism polynomials for patterns of pathwidth O(1)O(1) can also be written as such a combination for patterns of O(log⁡n)O(\log n)-forestwidth O(1)O(1). However, there are families of graphs of constant pathwidth and super-constant O(log⁡n)O(\log n)-forestwidth. Nonetheless, their homomorphism polynomials lie in symVAC1\mathrm{symVAC}^{1}.

Dawar, Pago, and Seppelt [DPS26a] introduced the non-uniform descriptive complexity monotonicity for ruling out such failures of homomorphism polynomials of distinct patterns to be linearly independent. For example, in order to show that a matrix-symmetric polynomial pnp_n is not in symVP\mathrm{symVP}, one may (recalling (1)) construct nn-vertex graphs GG and HH that are homomorphism indistinguishable over all graphs of treewidth ≤c\leq c, i.e., admit the same number of homomorphisms from every such graph, but differ in the value of pn(G)≠pn(H)p_n(G) \ne p_n(H). The construction of GG and HH in [DPS26a] crucially relies on the fact that the bound on the treewidth ≤c\leq c is constant while the host size nn is unbounded. It therefore cannot yield lower bounds as in Theorem 1.1 or lower bounds against symVACk\mathrm{symVAC}^{k} where ‘treewidth ≤c\leq c’ is replaced by ‘clog⁡knc\log^{k} n-forestwidth ≤c\leq c’, a condition depending on the host size nn. In Theorem 3.7, we overcome this issue using techniques from structural graph theory and homomorphism indistinguishability [51]. Our upgraded non-uniform descriptive complexity monotonicity supersedes [21 DPS26a] and has a more direct proof.

Future work

We highlight the following three directions for future work that may build on the results we have obtained. Firstly, our logarithmic depth reduction for pp-families (Theorem 4.1) raises the question of whether symmetric circuits can be reduced further, to depth 3 or 4, and at what cost in orbit size. In the classical setting, depth reduction began with balancing circuits [34, 57] and formulas [7, 8]. Later work gave sharper bounds for homogeneous formulas [Fou+26] and syntactically multilinear circuits [38]. The depth-four [2, 36, 55] and depth-three reductions over the rationals [29, 55] allow sufficiently strong lower bounds for shallow circuits to be lifted to general circuits. This is the motivation for seeking analogous reductions that preserve symmetry.

Another promising direction is to port the symmetry framework to algebraic proof complexity. In [Daw+25], a symmetric version of the Ideal Proof System (IPS), which is based on algebraic circuits, was introduced. Can symmetries be exploited in order to prove strong lower bounds against this proof system? An active recent line of work has established lower bounds for very restricted fragments of IPS, for example ro-ABP or constant depth multilinear IPS proofs [24 GHT+22, 30, 22]. A natural next step in this direction would be to attempt lower bounds for bounded depth symmetric IPS proofs. The machinery we have developed in this paper may serve as a tool to approach this problem.

Finally, we believe that our definition of the class symVBP\mathrm{symVBP} is a first step towards combining the symmetry-based lower bound approach with an ongoing programme on stronger (multilinear read-once oblivious) ABP lower bounds, e.g., [11, 4, 23]. Our definition and homomorphism polynomial characterisation of symmetric ABPs may be used in combination with other techniques to make new progress in this line of research, too.

Preliminaries

We work over a field K\mathbb{K} of characteristic zero. Write [n]={1,…,n}[n] = \{1,\ldots,n\} and let Sym⁡n\operatorname{Sym}_n be its permutation group. We follow the circuit and graph-polynomial conventions of [DPS26a; DPS26b].

Circuits and polynomial families

An algebraic circuit is a finite directed acyclic graph whose input gates are labelled by variables or field constants and whose internal gates are labelled by ++ or ×\times. Input gates with the same label are identified. We allow unbounded fan-in and parallel wires, counted with multiplicity in each operation. There is a unique output gate, and every gate lies on a path to it. The size is the number of gates and wires, counting multiplicities. The depth is the maximum number of wires on an input-to-output path. Likewise, the depth of a rooted tree or forest counts edges, so a single node has depth 0.

A formula has no parallel wires and its internal gates induce a tree; input gates may be shared. A circuit is skew if each multiplication gate has at most one incoming wire from an internal gate.

References

  1. [1]Isolde Adler, Eva Fluck, Tim Seppelt, and Gian Luca Spitzer. ‘Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth’. In: Logical Methods in Computer Science Volume 22, Issue 2, 33 (June 2026) (cited on pages 4, 11, 13, 44).DOI
  2. [2]Manindra Agrawal and V. Vinay. ‘Arithmetic Circuits: A Chasm at Depth Four’. In: 49th Annual IEEE Symposium on Foundations of Computer Science. 2008, pp. 67–75 (cited on page 6).DOI
  3. [3]Robert Andrews and Avi Wigderson. ‘Constant-Depth Arithmetic Circuits for Linear Algebra Problems’. In: SIAM Journal on Computing (Jan. 2026), FOCS24–236–FOCS24–295 (cited on pages 3, 11).
  4. [4]C. S. Bhargav, Prateek Dwivedi, and Nitin Saxena. ‘Lower bounds for the sum of small-size algebraic branching programs’. In: Theor. Comput. Sci. 1041 (2025), p. 115214 (cited on page 6).
  5. [6]Hans L. Bodlaender. ‘NC-algorithms for graphs with small treewidth’. In: Graph-Theoretic Concepts in Computer Science. Ed. by G. Goos et al. Vol. 344. Berlin, Heidelberg: Springer Berlin Heidelberg, 1989, pp. 1–10 (cited on page 12).DOI
  6. [7]Richard P. Brent. ‘The Parallel Evaluation of General Arithmetic Expressions’. In: Journal of the ACM 21.2 (Apr. 1974), pp. 201–206 (cited on pages 3, 6, 13).DOI
  7. [8]Nader H. Bshouty, Richard Cleve, and Wayne Eberly. ‘Size-Depth Tradeoffs for Algebraic Formulas’. In: SIAM Journal on Computing 24.4 (1995), pp. 682–705 (cited on page 6).
  8. [9]Peter Bürgisser. Completeness and Reduction in Algebraic Complexity Theory. Ed. by E. Becker, M. Bronstein, H. Cohen, D. Eisenbud, and R. Gilman. Vol. 7. Algorithms and Computation in Mathematics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000 (cited on page 19).DOI
  9. [10]Jin-Yi Cai, Martin Fürer, and Neil Immerman. ‘An optimal lower bound on the number of variables for graph identification’. In: Combinatorica 12.4 (1992), pp. 389–410 (cited on pages 11, 36, 46).
  10. [11]Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. ‘Lower Bounds for Set-Multilinear Branching Programs’. In: 39th Computational Complexity Conference, CCC 2024, Ann Arbor, MI, USA, July 22–25, 2024. Ed. by Rahul Santhanam. Vol. 300. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, 20:1–20:20 (cited on page 6).arxiv.org/abs/2312.15874
  11. [12]Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. ‘A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits’. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Paris, France: IEEE, Oct. 2018, pp. 934–945 (cited on page 1).arxiv.org/abs/1804.02520
  12. [13]Radu Curticapean. ‘Determinants from Homomorphisms’. In: 30th Annual European Symposium on Algorithms (ESA 2022). Vol. 244. Leibniz International Proceedings in Informatics (LIPIcs). 2022, 38:1–38:7 (cited on page 6).
  13. [16]Anuj Dawar, Tomáš Jakl, and Luca Reggio. ‘Lovász-Type Theorems and Game Co-monads’. In: 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS. IEEE, 2021, pp. 1–13 (cited on page 44).DOI
  14. [18]Anuj Dawar and Gregory Wilsenach. ‘Symmetric Arithmetic Circuits’. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Ed. by Artur Czumaj, Anuj Dawar, and Emanuela Merelli. Vol. 168. Leibniz International Proceedings in Informatics (LIPIcs). ISSN: 1868-8969. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, 36:1–36:18 (cited on pages 1, 3, 4).arxiv.org/abs/2002.06451
  15. [19]Anuj Dawar and Gregory Wilsenach. ‘Lower Bounds for Symmetric Circuits for the Determinant’. In: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Vol. 215. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 52:1–52:22 (cited on page 1).arxiv.org/abs/2107.10986
  16. [20]John D. Dixon and Brian Mortimer. Permutation Groups. Vol. 163. Graduate Texts in Mathematics. New York: Springer, 1996 (cited on page 27).
  17. [21]Prateek Dwivedi, Benedikt Pago, and Tim Seppelt. ‘Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials’. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing. Salt Lake City UT USA: ACM, June 2026, pp. 631–640 (cited on pages 1–11, 14, 17).
  18. [22]Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, and Iddo Tzameret. ‘Lower Bounds against the Ideal Proof System in Finite Fields’. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22–26, 2026. Ed. by Aditya Bhaskara and Artur Czumaj. ACM, 2026, pp. 1–12 (cited on page 6).arxiv.org/abs/2506.17210
  19. [23]Théo Borém Fabris, Nutan Limaye, Srikanth Srinivasan, and Amir Yehudayoff. ‘Multilinear Algebraic Branching Programs and the Min-Partition Rank Method’. In: 41st Computational Complexity Conference, CCC 2026, Lisbon, Portugal, August 3–6, 2026. Ed. by Dana Moshkovitz. Vol. 383. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, 22:1–22:20 (cited on page 6).DOI
  20. [24]Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson. ‘Proof Complexity Lower Bounds from Algebraic Circuit Complexity’. In: Theory Comput. 17 (2021), pp. 1–88 (cited on page 6).
  21. [27]Martin Grohe, Moritz Lichter, and Daniel Neuen. ‘The Iteration Number of the Weisfeiler-Leman Algorithm’. In: ACM Transactions on Computational Logic 26.1 (Jan. 2025), pp. 1–31 (cited on pages 2, 5, 12, 14, 43, 44, 47, 48).
  22. [28]Martin Grohe, Gaurav Rattan, and Tim Seppelt. ‘Homomorphism Tensors and Linear Equations’. In: Advances in Combinatorics (Apr. 2025) (cited on page 13).
  23. [29]Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. ‘Arithmetic Circuits: A Chasm at Depth 3’. In: SIAM J. Comput. 45.3 (2016), pp. 1064–1079 (cited on page 6).DOI
  24. [30]Tuomas Hakoniemi, Nutan Limaye, and Iddo Tzameret. ‘Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers’. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024. ACM, 2024, pp. 1396–1404 (cited on page 6).DOI
  25. [31]Johan Håstad. Computational limitations of small-depth circuits. Cambridge, MA, USA: MIT Press, 1987 (cited on page 2).
  26. [32]Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. ‘An Average-Case Depth Hierarchy Theorem for Boolean Circuits’. In: J. ACM 64.5 (2017), 35:1–35:27 (cited on page 2).DOI
  27. [33]Graham Higman. ‘On a conjecture of Nagata’. In: Mathematical Proceedings of the Cambridge Philosophical Society 52.1 (Jan. 1956). Ed. by P. Hall, pp. 1–4 (cited on page 13).DOI
  28. [34]Laurent Hyafil. ‘On the Parallel Evaluation of Multivariate Polynomials’. In: SIAM Journal on Computing 8.2 (May 1979), pp. 120–123 (cited on pages 6, 11).
  29. [35]Neeraj Kayal and Ramprasad Saptharishi. ‘A Selection of Lower Bounds for Arithmetic Circuits’. In: Perspectives in Computational Complexity. Ed. by Manindra Agrawal and Vikraman Arvind. Cham: Springer International Publishing, 2014, pp. 77–115 (cited on page 1).DOI
  30. [36]Pascal Koiran. ‘Arithmetic circuits: The chasm at depth four gets wider’. In: Theoretical Computer Science 448 (2012), pp. 56–65 (cited on page 6).arxiv.org/abs/1006.4700
  31. [37]Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. ‘Monotone Arithmetic Complexity of Graph Homomorphism Polynomials’. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Vol. 229. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 83:1–83:20 (cited on page 15).DOI
  32. [38]Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. ‘Towards Optimal Depth Reductions for Syntactically Multilinear Circuits’. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Vol. 132. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, 78:1–78:15 (cited on page 6).arxiv.org/abs/1902.07063
  33. [39]Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. ‘Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits’. In: Journal of the ACM 72.4 (2025), pp. 1–35. ECCC: TR21-081 (cited on pages 1, 3, 4).
  34. [40]Meena Mahajan. Algebraic Complexity Classes. arXiv:1307.3863 [cs]. Dec. 2013 (cited on page 15).arxiv.org/abs/1307.3863
  35. [41]Meena Mahajan and V. Vinay. ‘Determinant: Combinatorics, Algorithms, and Complexity’. In: Chicago Journal of Theoretical Computer Science 1997.5 (1997) (cited on page 21).
  36. [42]Guillaume Malod and Natacha Portier. ‘Characterizing Valiant’s Algebraic Complexity Classes’. In: Journal of Complexity 24.1 (2008), pp. 16–38 (cited on page 19).
  37. [43]Laura Mančinska and David E. Roberson. ‘Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs’. In: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 2020, pp. 661–672 (cited on page 13).
  38. [45]Daniel Neuen and Tim Seppelt. ‘Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs’. In: 41st Annual Symposium on Logic in Computer Science (LICS 2026). Ed. by Claudia Faggian and Joost-Pieter Katoen. Vol. 380. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, 75:1–75:29 (cited on page 35).
  39. [46]C Procesi. ‘The invariant theory of n × n matrices’. In: Advances in Mathematics 19.3 (Mar. 1976), pp. 306–381 (cited on page 13).DOI
  40. [47]Ran Raz. ‘Multi-linear formulas for permanent and determinant are of super-polynomial size’. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13–16, 2004. Ed. by László Babai. ACM, 2004, pp. 633–641 (cited on page 1).
  41. [48]Ran Raz. ‘Separation of Multilinear Circuit and Formula Size’. In: Theory Comput. 2.6 (2006), pp. 121–135 (cited on page 2).
  42. [49]Ran Raz and Amir Yehudayoff. ‘Lower Bounds and Separations for Constant Depth Multilinear Circuits’. In: Comput. Complex. 18.2 (2009), pp. 171–207 (cited on page 1).
  43. [50]Ju P Razmyљslov. ‘Trace Identities of Full Matrix Algebras Over a Field of Characteristic Zero’. In: Mathematics of the USSR-Izvestiya 8.4 (Aug. 1974), pp. 727–760 (cited on page 13).DOI
  44. [51]David E. Roberson. ‘Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree’. In: Journal of Combinatorial Theory, Series B 181 (Nov. 2026), pp. 1–61 (cited on pages 2, 6, 11, 33, 35, 36).arxiv.org/abs/2206.10321
  45. [52]Tim Seppelt. ‘Homomorphism Indistinguishability’. Dissertation. Aachen: RWTH Aachen University, 2024 (cited on pages 11, 13).DOI
  46. [53]Tim Seppelt. ‘Logical equivalences, homomorphism indistinguishability, and forbidden minors’. In: Information and Computation 301 (Dec. 2024), p. 105224 (cited on pages 11, 38).
  47. [54]Michael Sipser. ‘Borel Sets and Circuit Complexity’. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA. Ed. by David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas. ACM, 1983, pp. 61–69 (cited on page 2).DOI
  48. [55]Sébastien Tavenas. ‘Improved bounds for reduction to depth 4 and depth 3’. In: Inf. Comput. 240 (2015), pp. 2–11 (cited on page 6).
  49. [56]L. G. Valiant. ‘Completeness classes in algebra’. In: Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC ’79. Atlanta, Georgia, United States: ACM Press, 1979, pp. 249–261 (cited on page 1).DOI
  50. [57]L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. ‘Fast Parallel Computation of Polynomials Using Few Processors’. In: SIAM Journal on Computing 12.4 (Nov. 1983), pp. 641–644 (cited on pages 3, 6, 11, 12).
  51. [58]Leslie G. Valiant. ‘Reducibility by Algebraic Projections’. In: Logic and Algorithmic: An International Symposium Held in Honor of Ernst Specker. Vol. 30. Monographies de L’Enseignement Mathématique. 1982, pp. 365–380 (cited on page 19).

Paper details

vlnc:W_hsp8ue8g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Sonnet 5.5 (bare), Claude Opus 5.5 (bare), Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents