Monotone Bounded-Depth Complexity of Homomorphism Polynomials

C. S. Bhargav; Prateek Dwivedi; Radu Curticapean; Shiteng Chen

REVIEW 4 major objections 4 minor 1 cited by

Monotone Bounded-Depth Complexity of Homomorphism Polynomials

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

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

Pith's one-line read A new graph parameter, pruned $\Delta$-treewidth, exactly sets the exponent of bounded-depth monotone circuits for homomorphism polynomials.

desk verdict Main theorem 1.2 is false as stated for stars because degree-1 pruning drops the parameter to 0 while the polynomial still needs n^2 input gates; the framework is promising and likely fixable, but the paper needs a real repair. read the letter →

arxiv 2505.22894 v1 pith:OYP72VSZ submitted 2025-05-28 cs.CC cs.DM

C. S. Bhargav , Shiteng Chen , Radu Curticapean , Prateek Dwivedi This is my paper

classification cs.CCcs.DM MSC 68Q1768Q1505C85

keywords monotonecircuitsbounded-depthhomomorphismpolynomialstreewidthtree-decompositionalgebraiccomplexitydepthhierarchygraph

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

The paper claims that for every fixed graph $H$ and every $\Delta$, the smallest monotone circuit of product-depth $\Delta$ computing the homomorphism polynomial of $H$ has size $\Theta(n^{\mathrm{ptw}_\Delta(H)+1})$, where $\mathrm{ptw}_\Delta(H)$ is the pruned $\Delta$-treewidth: the minimum width of a tree-decomposition of $H^\dagger$, the graph obtained from $H$ by deleting all degree-$1$ vertices, with the underlying tree required to have height at most $\Delta$. The same exact exponent holds for the colorful subgraph polynomial, and an analogous statement replaces treewidth by pathwidth for monotone algebraic branching programs of length $\Delta$. The paper further proves an optimal depth hierarchy: for every $n$ and $\Delta$ there is a graph $H_\Delta$ of size $\Theta(n)$ whose colorful subgraph polynomial is computable by monotone circuits of product-depth $\Delta+1$ in polynomial size, yet requires size $n^{\Omega(n^{1/\Delta})}$ at product-depth $\Delta$. The reason this matters is that it pins down the precise exponent of a natural algebraic model with matching upper and lower bounds, and it derives a sharp depth hierarchy from a purely graph-theoretic parameter.

What carries the argument

The load-bearing object is the pruned $\Delta$-treewidth $\mathrm{ptw}_\Delta(H)$, defined as the minimum width of a tree-decomposition whose underlying tree has height at most $\Delta$, applied to $H^\dagger$, the graph obtained from $H$ by deleting all degree-$1$ vertices. The upper bound is built by dynamic programming over such a decomposition: an edge-representation assigns each edge of $H$ to a bag containing it, and the product-depth of the resulting circuit is exactly the number of 'active' nodes on any root-to-leaf path (nodes that either multiply several represented edges, have multiple children, or represent an edge and have a child). The lower bound uses Claim 5.2, which extracts from any monotone parse tree of product-depth $\Delta$ computing a monomial a tree-decomposition of $H^\dagger$ of height $\Delta$; since the decomposition has a bag of size $\mathrm{ptw}_\Delta(H)+1$, the corresponding gate can appear in at most $n^{k-\mathrm{ptw}_\Delta(H)-1}$ parse trees, forcing $n^{\mathrm{ptw}_\Delta(H)+1}$ distinct gates. A transfer lemma (Lemma 5.1) converts circuits between $\mathrm{Hom}_{H,n}$ and $\mathrm{ColSub}_{H,n}$ without changing product-depth, so the characterization applies to both polynomials.

What would settle it

Take $H = K_{1,4}$ (a star), so $H^\dagger$ is empty, and run the marking procedure of Claim 5.2 on any monotone parse tree of product-depth $2$ for $\mathrm{ColSub}_{H,n}$; if the extracted object contains a nonempty bag, or if for any $H$ with degree-$1$ vertices the extracted tree has height $\Delta+1$ rather than $\Delta$, the extraction lemma and the lower bound it supports are false.

Watch

Extended reading notes

Core claim

The paper's central discovery is a tight, parameter-exact characterization: for every fixed graph $H$ and every $\Delta$, the homomorphism polynomial $\mathrm{Hom}_{H,n}$ and its set-multilinear relative $\mathrm{ColSub}_{H,n}$ are computable by monotone circuits of product-depth $\Delta$ with $O(n^{\mathrm{ptw}_\Delta(H)+1})$ gates, and every monotone circuit of product-depth $\Delta$ computing either polynomial has $\Omega(n^{\mathrm{ptw}_\Delta(H)+1})$ gates, where $\mathrm{ptw}_\Delta(H)$ is the pruned $\Delta$-treewidth of $H$: the minimum width of a tree-decomposition of the graph obtained from $H$ by deleting all degree-$1$ vertices, with the underlying tree required to have height at most $\Delta$. The same statement holds for monotone algebraic branching programs with length $\Delta$ in terms of pruned $\Delta$-pathwidth. The paper also constructs, for each $n$ and $\Delta$, a graph $H_\Delta$ of size $\Theta(n)$ whose colorful subgraph polynomial can be computed by monotone product-depth $\Delta+1$ circuits of polynomial size, yet any monotone product-depth $\Delta$ circuit requires size $n^{\Omega(n^{1/\Delta})}$, giving an optimal depth hierarchy for monotone circuits.

Load-bearing premise

The lower bound rests on the extraction lemma (Claim 5.2), which asserts that every monotone parse tree of product-depth $\Delta$ computing a monomial of $\mathrm{ColSub}_{H,n}$ yields a genuine tree-decomposition of the pruned graph $H^\dagger$ whose underlying tree has height at most $\Delta$; if the marking scheme fails to preserve connectedness or the height bound is off, the counting argument behind the $\Omega(n^{\mathrm{ptw}_\Delta(H)+1})$ lower bound collapses.

Editorial extensions

If this is right

For every fixed $H$, the exact size exponent of monotone product-depth-$\Delta$ circuits for $\mathrm{Hom}_{H,n}$ and $\mathrm{ColSub}_{H,n}$ is $\mathrm{ptw}_\Delta(H)+1$, leaving no slack in the exponent.
The analogous result for monotone algebraic branching programs of length $\Delta$ is governed by the pruned $\Delta$-pathwidth $\mathrm{ppw}_\Delta(H)$.
There exist polynomials computable in polynomial size at product-depth $\Delta+1$ that require size $n^{\Omega(n^{1/\Delta})}$ at product-depth $\Delta$, and by standard depth reduction this bound is optimal, giving the first optimal monotone depth hierarchy of this form.
For bounded-depth monotone computation, degree-$1$ vertices of $H$ do not affect the complexity; only the pruned core $H^\dagger$ matters.
The depth-hierarchy theorem is unconditional, so it separates monotone bounded-depth algebraic complexity classes without relying on the exponential-time hypothesis.

Reading between the lines

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

Editorial inference: the parse-tree extraction method is not tied to circuits specifically; the same accounting of active nodes could yield tight bounds for monotone formulas or multilinear bounded-depth models, where the corresponding branching measure would replace product-depth.
Editorial inference: $\mathrm{ptw}_\Delta(H)$ gives a graded family of width measures interpolating between vertex-cover number ($\Delta=2$) and treewidth (large $\Delta$), so the theorem suggests that other natural width parameters may be characterized by shallow tree-decompositions and appear as exponents in related counting problems.
Editorial inference: the paper notes its transfer lemma is exponential in $|E(H)|$, so the depth-hierarchy construction does not directly yield the same optimal hierarchy for the ordinary homomorphism polynomial $\mathrm{Hom}_{H,n}$ when $|H|$ grows; closing that gap would be a natural continuation.
Editorial inference: because the lower bounds are unconditional, the hierarchy theorem provides a concrete separation of monotone algebraic complexity classes at small depths that does not rely on hardness assumptions such as the exponential-time hypothesis.

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

First, the thing you should know: Theorem 1.2, the central characterization, is false as written. Take H=K_{1,3}. The pruned graph H† is a single vertex, so ptw_Δ(H)=0 for every Δ. The theorem then promises monotone circuits of size O(n) and product-depth Δ. But Hom_{K_{1,3},n} = Σ_{i∈[n]} (Σ_{j∈[n]} x_{i,j})^3, which depends on all n^2 variables; any circuit must have n^2 input gates, so size Ω(n^2). The paper's own upper-bound construction gives O(n^2) here, not O(n). The cause is the degree-1 pruning: leaves force bags of size at least 2, so when the pruned graph has treewidth 0 the exponent gets an extra +1. This is not a typo; it breaks the main theorem. The stress-test is right, and the reader's report missed it.

What is genuinely good: the Δ-treewidth and Δ-pathwidth parameters are natural bounded-depth variants, the dynamic-programming upper bound from bounded-height tree-decompositions is clean, and the lower-bound idea of extracting a tree-decomposition from a parse tree is a clever adaptation of KPR23. The depth-hierarchy construction using full d-ary trees (Theorem 3.5) is also nice, and the paper is honest about limitations.

Now the other soft spots. The proof of Theorem 6.1 writes an upper bound of O(n^{|H_Δ|}) for product-depth Δ+1, which is not poly(n) when |H_Δ|=Θ(n). The correct bound from Lemma 4.1 is O(|V(T)|·n^2); with |V(T)|=Θ(n) that gives poly(n), so the hierarchy theorem is probably salvageable but the write-up is wrong. Lemma 5.1, the derivative trick transferring between Hom and ColSub, is sketched; I want the depth accounting written out in full. Claim 5.2's marking scheme also deserves scrutiny: the height bound of exactly Δ could easily be off by one, and the counting argument downstream depends on it.

Bottom line: this is a promising framework attached to a false main theorem. The fix is likely simple — state the exponent as max(ptw_Δ(H),1)+1 or adjust the pruning parameter — but until that is done, the paper cannot be accepted as is. I would still send it to a serious referee: the ideas are worth careful review, the counterexample is instructive, and with the repair it could be a solid paper.

Referee Report

4 major / 4 minor

Summary. The paper introduces bounded-depth variants of treewidth and pathwidth, defines the pruned parameters ptw_Δ and ppw_Δ, and claims that monotone circuits of product-depth Δ computing the homomorphism polynomial Hom_{H,n} and the colorful subgraph polynomial ColSub_{H,n} have size Θ(n^{ptw_Δ(H)+1}), with a parallel ABP statement. The upper bound is proved via a dynamic program on a bounded-height tree-decomposition, and the lower bound via extraction of a tree-decomposition from parse trees. The paper further claims a depth-hierarchy theorem based on full d-ary trees. The central exact-characterization theorem is, however, false as stated: for H=K_{1,3}, the pruned graph is K1, ptw_Δ(H)=0, and the claimed O(n) size is impossible because the polynomial depends on n^2 variables. The same phenomenon affects the lower-bound proof and the hierarchy theorem as written.

Significance. The proposed notion of Δ-treewidth is natural and the dynamic-programming/parse-tree framework is well matched to the problem; if the errors were repaired, the paper would give an interesting bounded-depth analogue of the treewidth characterization of Komarath, Pandey and Rahul. The paper also contains detailed proofs and a useful transfer lemma between Hom and ColSub in bounded depth. However, because the main theorem is contradicted by an elementary star example and the hierarchy theorem's exponent appears miscalculated, the significance of the current version is substantially compromised.

major comments (4)

[Theorem 1.2 / Definition 3.2] The main result is false as stated. Let H=K_{1,3}. Since H† is obtained by deleting all degree-1 vertices, H†=K1, so tw_Δ(H†)=0 and ptw_Δ(H)=0 for every Δ. Theorem 1.2 therefore predicts monotone circuits of product-depth Δ and size O(n). But Hom_{K_{1,3},n} = Σ_{i∈[n]} (Σ_{j∈[n]} x_{i,j})^3, which depends on all n^2 variables x_{i,j}. By Definition 2.1, circuit size counts vertices, so every circuit computing this polynomial has at least n^2 input gates and hence size Ω(n^2). This also agrees with the known Θ(n^{tw(H)+1})=Θ(n^2) bound of KPR23. The exact exponent characterization in Theorem 1.2 is therefore false for every graph with at least one edge whose pruned Δ-treewidth is 0.
[Section 4, upper-bound proof after Lemma 4.1] The proof of the claimed upper bound does not deliver O(n^{ptw_Δ+1}) for the star example. For H=K_{1,3}, a degree-1 leaf v with neighbor u forces a bag {u,v} of size 2 in any tree-decomposition of H, even though H†=K1 has width 0. Inserting the leaves as described gives a tree-decomposition of H of width 2, and Lemma 4.1 then yields size O(n^2), not O(n). Thus the assertion that degree-1 vertices can be removed 'safely' is only valid when the core already has Δ-treewidth at least 1; for tw_Δ(H†)=0 the exponent should be 1, not 0.
[Theorem 5.3 / Section 5.2] The lower-bound proof is also inconsistent with the star example. When ptw_Δ(H)=0, Theorem 5.3 concludes Ω(n), but the true bound is Ω(n^2) from input gates alone. The shared-gate counting argument only counts gates corresponding to bags of the extracted tree-decomposition; it does not account for the input gates that must feed those gates. In the natural circuit Σ_i (Σ_j x_{i,j})^3, the n multiplication gates are each shared by n^3 monomials, which yields only the bound Ω(n); the dominant Ω(n^2) input-gate cost is invisible to the argument. I did not find a separate flaw in Claim 5.2; the collapse occurs in the subsequent gate-counting step of Theorem 5.3.
[Theorem 6.1 / Theorem 1.4] The hierarchy theorem is not proved as stated. The proof sets HΔ=T_{Δ+2} and asserts d=Θ(|HΔ|^{1/Δ}); however |V(T_{Δ+2})| = Θ(d^{Δ+2}), so d=Θ(|HΔ|^{1/(Δ+2)}), not Θ(|HΔ|^{1/Δ}). Consequently the lower bound obtained is n^{Ω(|HΔ|^{1/(Δ+2)})}, which for |HΔ|=Θ(n) is n^{n^{1/(Δ+2)}}, weaker than the claimed n^{Ω(n^{1/Δ})}. In addition, the stated upper bound O(n^{|HΔ|}) in Theorem 6.1 is not poly(n) when |HΔ|=Θ(n), so the sentence deriving Theorem 1.4 from Theorem 6.1 is invalid; the intended poly(n) upper bound would have to come from ptw_{Δ+1}=1 via a corrected version of Theorem 1.2.

minor comments (4)

[Section 4] The sentence explaining that the rep-height is at most Δ even though the height of T' may be Δ+1 is easy to misread as a claim about the height of the tree-decomposition; it should be restated explicitly in terms of the active-node definition.
[Figure 1] The notation with dots over vertices such as {˙1,2,4} is not explained in the caption; please clarify that dotted vertices are the marked degree-1 vertices that are later dropped.
[Section 3.1] The connection between 2-treewidth and vertex integrity is mentioned only parenthetically; a precise statement of the equality would help the reader verify the claimed exponent for Δ=2.
[Theorem 1.3] The condition Δ≥|E(H)| is stated but its role in the lower-bound proof is never discussed; please indicate where this condition is used.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: ptw_Δ is an independently defined graph parameter, the upper and lower bounds are proved from tree-decompositions and parse trees, and the only imported external result is KPR23, whose authors do not overlap with the present paper.

full rationale

The paper's derivation chain is self-contained rather than circular. The pruned Δ-treewidth ptw_Δ(H) is defined purely graph-theoretically as the Δ-treewidth of the graph H† obtained by deleting degree-1 vertices, with no reference to circuit size or to the polynomials HomH,n and ColSubH,n. The upper bound in Theorem 1.2 is obtained by taking a height-Δ tree-decomposition of H†, adding leaf bags for deleted degree-1 vertices, and applying Lemma 4.1, which constructs circuits of size O(|V(T)|·n^w) and product-depth equal to a rep-height that is bounded by Δ. The lower bound in Theorem 5.3 is proved by extracting a tree-decomposition of H† from a parse tree (Claim 5.2) and then using a monomial-counting argument: a bag of size ptw_Δ(H)+1 yields a gate that can appear in at most n^{k-(t+1)} monomials, forcing Ω(n^{t+1}) gates. This is a genuine combinatorial argument, not a restatement of the theorem. The reduction between HomH,n and ColSubH,n is imported from Komarath, Pandey and Rahul (KPR23), an external source with no author overlap, and it is used only to transfer results, not to assume the bounded-depth exponent. The self-citations in the paper ([BDS24], [Cur+25]) appear only as background references in the introduction and are not load-bearing for the main theorems. No fitted parameters are renamed as predictions, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in by citation. The skeptic brief's star counterexample, if valid, would be a correctness gap in the width accounting of the upper-bound construction — the added leaf bags for K_{1,3} have size 2 even though tw_Δ(K_1)=0 — but that is a mathematical error in the proof, not an instance of circular reasoning. The circularity pass therefore returns 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted to data; the only inputs are the fixed graph H, the size parameter n, and the depth bound Δ. The proofs rely on standard properties of tree decompositions, parse trees, and monotone circuits. The derivative computation in Lemma 5.1 is a technical assumption that is only sketched.

assumptions (3)

standard math Parse trees of monotone circuits compute monomials without cancellation; every reduced parse tree corresponds to a monomial and vice versa.
Used throughout Section 5, especially in the lower-bound proofs, to relate circuit gates to monomials and to rule out spurious monomials via monotonicity.
domain assumption Partial derivatives of a circuit can be computed by a circuit of size O(s|E(H)|) and the same product-depth, as claimed in Lemma 5.1.
This is a non-trivial Baur-Strassen-style claim with only a sketchy proof; if it fails, the transfer between HomH,n and ColSubH,n at equal product-depth breaks.
standard math The separator property of tree-decompositions: for a node p, the bag X_p separates the cones of different children in the decomposition.
Used in Lemma 4.1 to justify independent choices of homomorphisms on the cones below each child.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Monotone Bounded-Depth Complexity of Homomorphism Polynomials." pith.science (2026). https://pith.science/paper/OYP72VSZ

@misc{pith2026250522894,
  author       = {Pith},
  title        = {Pith review of: Monotone Bounded-Depth Complexity of Homomorphism Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OYP72VSZ}},
  note         = {Machine review of arXiv:2505.22894}
}

abstract

For every fixed graph $H$, it is known that homomorphism counts from $H$ and colorful $H$-subgraph counts can be determined in $O(n^{t+1})$ time on $n$-vertex input graphs $G$, where $t$ is the treewidth of $H$. On the other hand, a running time of $n^{o(t / \log t)}$ would refute the exponential-time hypothesis. Komarath, Pandey and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph $\textit{polynomials}$ for fixed graphs $H$. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the $\textit{monotone}$ circuit complexity of the homomorphism polynomial for $H$ is $\Theta(n^{\mathrm{tw}(H)+1})$. In this paper, we characterize the power of monotone $\textit{bounded-depth}$ circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters $\mathrm{tw}_\Delta(H)$, for fixed $\Delta \in \mathbb N$, which capture the width of tree-decompositions for $H$ when the underlying tree is required to have depth at most $\Delta$. We prove that monotone circuits of product-depth $\Delta$ computing the homomorphism polynomial for $H$ require size $\Theta(n^{\mathrm{tw}_\Delta(H^{\dagger})+1})$, where $H^{\dagger}$ is the graph obtained from $H$ by removing all degree-$1$ vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

Figures

Figures reproduced from arXiv: 2505.22894 by the authors.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
cs.CC 2025-11 conditional novelty 7.0 of 10

Monotone bounded-depth formula size for graph homomorphism polynomials equals n^{λ_Δ(H)}, where λ_Δ(H) is the minimum cost of a baggy elimination tree of product depth Δ.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · cited by 1 Pith paper

[26]

Progr. Comput. Sci. Appl. Logic. Birkhäuser/Springer, Cham, 2014, pp. 51–75 (cit. on p. 7). [Mar10] Dániel Marx. Can you beat treewidth? In: Theory of Computing. An Open Access Journal 6 (2010), pp. 85–112 (cit. on p. 2). [MP08] Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. In: Journal of Complexity 24.1 (2008...

work page 2010
[55]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 89, 12 (cit. on p. 4). [IP01] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. In: Journal of Computer and System Sciences 62 (2001), pp. 367–375 (cit. on p. 2). [JS82] Mark Jerrum and Marc Snir. Some exact complexity results for straigh...

work page 2001
[57]

Leibniz Int

LIPIcs. Leibniz Int. Proc. In- form. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 28, 17 (cit. on pp. 5, 9). [CKR22] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. In: Algorithmica. An International Journal in Computer Science 84.12 (2022), pp. 3655–3685 (cit. on p. 4...

work page 2022
[85]

Lecture Notes in Comput. Sci. Springer, Berlin-New York, 1980, pp. 621–631 (cit. on p. 4). 21 [Sri20] Srikanth Srinivasan. Strongly exponential separation between monotone VP and monotone VNP. In: ACM Transactions on Computation Theory 12.4 (2020), Art. 23, 12 (cit. on p. 4). [SY09] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: a survey of recent...

work page 2020
[261]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023, Art. No. 12, 20 (cit. on p. 5). [AV08] Manindra Agrawal and V . Vinay. Arithmetic circuits: A chasm at depth four . In: 49th annual IEEE symposium on Foundations of Computer Science (FOCS). IEEE Computer So- ciety, 2008, pp. 67–75 (cit. on p. 4). [BDS24] C. S. Bharga...

work page 2024
[306]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. In- form., Wadern, 2024, Art. No. 6, 18 (cit. on p. 5). [All+98] Eric Allender, Jia Jiao, Meena Mahajan, and V . Vinay. Non-commutative arithmetic cir- cuits: Depth reduction and size lower bounds. In: Theoretical Computer Science209.1-2 (1998), pp. 47–86 (cit. on p. 7). 18 [Ami+23] Prasha...

work page 1998
[327]

Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 28:1–28:24 (cit

LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 28:1–28:24 (cit. on p. 2). [DJ04] Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. In: Theoretical Computer Science 329.1-3 (2004), pp. 315–323 (cit. on p. 2). [Dur+16] Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre,...

work page 2004
[1450]

Lecture Notes in Comput. Sci. Springer, Berlin, 1998, pp. 702–712 (cit. on p. 5). [CDM17] Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs . In: STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 2017, pp. 210–223 (cit. on p. 2). [Chi+18] Suryajith C...

work page 1998

Show all 11 references

[2014]

130– 139 (cit

IEEE Computer Soc., Los Alamitos, CA, 2014, pp. 130– 139 (cit. on p. 2). [CM16] Hubie Chen and Stefan Mengel. Counting answers to existential positive queries: A com- plexity classification . In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI sympo- sium on principles of data...

2014
[2016]

by Tova Milo and Wang-Chiew Tan

Ed. by Tova Milo and Wang-Chiew Tan. ACM, 2016, pp. 315–326 (cit. on p. 2). [Cur+25] Radu Curticapean, Simon Döring, Daniel Neuen, and Jiaheng Wang. Can you link up with treewidth? In: 42nd international Symposium on Theoretical Aspects of Computer Science (STACS). Vol

2016
[2021]

804–814 (cit

IEEE Computer Soc., Los Alamitos, CA, 2021, pp. 804–814 (cit. on p. 5). [Mah14] Meena Mahajan. Algebraic complexity classes. In: Perspectives in computational complexity. Vol

2021

Pith tools

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

[1] [26]

Progr. Comput. Sci. Appl. Logic. Birkhäuser/Springer, Cham, 2014, pp. 51–75 (cit. on p. 7). [Mar10] Dániel Marx. Can you beat treewidth? In: Theory of Computing. An Open Access Journal 6 (2010), pp. 85–112 (cit. on p. 2). [MP08] Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. In: Journal of Complexity 24.1 (2008...

work page 2010

[2] [55]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 89, 12 (cit. on p. 4). [IP01] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. In: Journal of Computer and System Sciences 62 (2001), pp. 367–375 (cit. on p. 2). [JS82] Mark Jerrum and Marc Snir. Some exact complexity results for straigh...

work page 2001

[3] [57]

Leibniz Int

LIPIcs. Leibniz Int. Proc. In- form. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 28, 17 (cit. on pp. 5, 9). [CKR22] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. In: Algorithmica. An International Journal in Computer Science 84.12 (2022), pp. 3655–3685 (cit. on p. 4...

work page 2022

[4] [85]

Lecture Notes in Comput. Sci. Springer, Berlin-New York, 1980, pp. 621–631 (cit. on p. 4). 21 [Sri20] Srikanth Srinivasan. Strongly exponential separation between monotone VP and monotone VNP. In: ACM Transactions on Computation Theory 12.4 (2020), Art. 23, 12 (cit. on p. 4). [SY09] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: a survey of recent...

work page 2020

[5] [261]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023, Art. No. 12, 20 (cit. on p. 5). [AV08] Manindra Agrawal and V . Vinay. Arithmetic circuits: A chasm at depth four . In: 49th annual IEEE symposium on Foundations of Computer Science (FOCS). IEEE Computer So- ciety, 2008, pp. 67–75 (cit. on p. 4). [BDS24] C. S. Bharga...

work page 2024

[6] [306]

Leibniz Int

LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. In- form., Wadern, 2024, Art. No. 6, 18 (cit. on p. 5). [All+98] Eric Allender, Jia Jiao, Meena Mahajan, and V . Vinay. Non-commutative arithmetic cir- cuits: Depth reduction and size lower bounds. In: Theoretical Computer Science209.1-2 (1998), pp. 47–86 (cit. on p. 7). 18 [Ami+23] Prasha...

work page 1998

[7] [327]

Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 28:1–28:24 (cit

LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 28:1–28:24 (cit. on p. 2). [DJ04] Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. In: Theoretical Computer Science 329.1-3 (2004), pp. 315–323 (cit. on p. 2). [Dur+16] Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre,...

work page 2004

[8] [1450]

Lecture Notes in Comput. Sci. Springer, Berlin, 1998, pp. 702–712 (cit. on p. 5). [CDM17] Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs . In: STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 2017, pp. 210–223 (cit. on p. 2). [Chi+18] Suryajith C...

work page 1998