Pith. sign in

REVIEW 3 major objections 4 minor 7 references

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

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

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

Pith's one-line read For any connected pattern graph H with more than two vertices, the smallest monotone formula of product depth Δ computing the colored isomorphism polynomial ColIso_H has size Θ(n^{λ_Δ(H)}), where λ_Δ(H) is the minimum cost of a baggy elimin

desk verdict A genuinely new characterization of bounded-depth monotone formula complexity via baggy elimination trees, with a fixable but load-bearing definitional error and off-by-one mistakes in the applications. read the letter →

arxiv 2511.03388 v2 pith:6TS4V5ZL submitted 2025-11-05 cs.CC

Balagopal Komarath , Rohit Narayanan This is my paper
classification cs.CC MSC 68Q1768Q15
keywords graphhomomorphismpolynomialscoloredisomorphismbaggyeliminationtreebounded-depthmonotoneformulastreedepthcircuitvsformulaseparationalgebraiccomplexityproductdepth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper pins down the exact (up to constant factors) size of monotone arithmetic formulas of bounded product depth that compute the colored isomorphism polynomial of a pattern graph H. It introduces baggy elimination trees, a generalization of the elimination trees behind treedepth, and defines λ_Δ(H) as the cheapest such tree of product depth Δ. The main theorem states that the Δ-product depth monotone formula complexity of ColIso_H is Θ(n^{λ_Δ(H)}) for every connected H with more than two vertices. This completes a program that had already characterized monotone circuits by (bounded-depth) treewidth and monotone algebraic branching programs by (bounded-depth) pathwidth, leaving formulas as the last model. The characterization yields a near-optimal circuit-vs-formula separation at every fixed product depth and a strict depth hierarchy for monotone formulas.

What carries the argument

Baggy elimination trees: a rooted tree whose nodes carry bags (subsets of vertices of H) covering V(H), such that every edge of H appears either inside one bag or across ancestor-descendant bags. The cost of a root-to-leaf path is the sum of its bag sizes; product depth counts internal nodes on the path, with non-core leaves (bags containing only pendant vertices) excluded. λ_Δ(H) is the minimum over all baggy elimination trees of product depth at most Δ of the maximum path cost. This parameter does the work of the proof: the upper bound converts an optimal tree directly into a formula, and the lower bound converts any parse tree into a tree with cost bounded by the exponent of n, forcing th

What would settle it

Take a small pattern such as the 4-cycle C_4 and compute λ_2(C_4) under the one-way reading; then determine the true minimum size of a product-depth-2 monotone formula for ColIso_{C_4}. If the exponent of n in that size is not λ_2(C_4), the main theorem is false.

Watch

Extended reading notes

Core claim

The paper's central claim is that the bounded-depth monotone formula complexity of the colored isomorphism polynomial ColIso_H is governed exactly by a new graph parameter, λ_Δ(H). A baggy elimination tree for H is a rooted tree in which each node carries a bag of vertices of H and every edge of H has its two endpoints in the same bag or in ancestor-descendant bags; the product depth is the maximum number of internal nodes on a root-to-leaf path (excluding leaves that contain only pendant vertices), and the cost of a path is the sum of its bag sizes. λ_Δ(H) is the minimum possible cost of any such tree with product depth at most Δ. Theorem 1 proves that the Δ-product depth monotone formula s

Load-bearing premise

The theorem stands or falls with the intended one-way reading of a baggy elimination tree: every edge of H must be covered by a bag or by ancestor-descendant bags, but non-edges may also sit in such positions; the printed 'if and only if' would define a different parameter and break the Θ(n^{λ_Δ(H)}) result.

Editorial extensions

If this is right

  • For every fixed connected H with more than two vertices, the Δ-product-depth monotone formula size of ColIso_H is Θ(n^{λ_Δ(H)}), so the graph parameter completely determines the exponent.
  • The characterization completes the programme that had already linked monotone circuits to treewidth variants and monotone ABPs to pathwidth variants, leaving formulas as the final model.
  • Theorem 2 gives a near-optimal circuit-vs-formula separation: at every fixed product depth, some constant-degree family has O(N)-size monotone circuits of depth Δ but requires Ω(N^{Δ/2})-size monotone formulas of the same depth.
  • Theorem 4 establishes a strict depth hierarchy: for any Δ≥1 and constant k≥2, a constant-degree family can be computed by O(s(N))-size formulas of depth Δ but requires Ω(s(N)^k)-size formulas of depth Δ−1.
  • Because λ_Δ(H) is always at most the treedepth of H, the new parameter refines treedepth and recovers the known unbounded-depth treedepth characterization as a special case.

Reading between the lines

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

  • A natural next step is to study the complexity of computing λ_Δ(H); an efficient algorithm for fixed Δ would turn the characterization into a practical predictor of monotone formula size for a given pattern H.
  • This suggests the parse-tree-to-decomposition lower bound is transferable: other polynomials whose monomials are products indexed by the edges of a pattern graph (e.g., subgraph polynomials) should exhibit the same λ_Δ characterization.
  • The near-tight circuit-vs-formula gap suggests that the real obstruction is the gap between bounded-depth treewidth and the new baggy-elimination-tree cost; graphs where those two parameters diverge more sharply may yield even stronger separations than the ones proven here.
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.

Referee Report

3 major / 4 minor

Summary. The paper introduces the notion of a baggy elimination tree (BET), a generalization of elimination trees in which each node carries a bag of vertices, together with two parameters: product depth and cost. It defines λ_Δ(H) as the minimum cost of a BET for H of product depth at most Δ, and claims in Theorem 1 that the Δ-product-depth monotone formula complexity of the coloured isomorphism polynomial ColIso_H is Θ(n^{λ_Δ(H)}) for every connected H on more than two vertices. The upper bound is proved by a recursive formula whose structure mirrors a BET; the lower bound is proved by lifting a parse tree to a BET. The paper then derives two applications: a separation between bounded-depth monotone circuits and formulas, and a depth hierarchy for monotone formulas.

Significance. If Theorem 1 is correct, it supplies the missing bounded-depth formula characterization in the programme of Komarath–Pandey–Rahul and Bhargav–Chen–Curticapean–Dwivedi, and the BET cost is a new graph parameter that connects monotone formula complexity to tree structure. The proof strategy is plausible and the lower-bound construction is nontrivial. However, as written the paper contains a load-bearing inconsistency in the central definition and off-by-one errors in both application sections. The central theorem appears defensible after a local fix, but the advertised applications are not established as stated.

major comments (3)
  1. [Section 3, Definition 7] Definition 7 requires that {u,v} ∈ E(H) if and only if u and v are in the same bag or in ancestor-descendant bags. This is internally contradicted by Example 1 and Figure 1: the root bag {2,4,6} contains non-adjacent vertices, and non-adjacent pairs such as (1,4) are in ancestor-descendant bags. The parse-tree lifting in Section 4 (Figure 2) also places non-adjacent vertices in comparable bags. All proofs use only the forward direction: every edge must have its endpoints in the same bag or in ancestor-descendant bags. Under the literal 'iff' definition, the example tree is invalid and λ_Δ is a different, larger parameter; Theorem 1 would not apply. The definition must be changed to the one-way condition. This is load-bearing for the main theorem.
  2. [Section 5, Theorem 2] The text states that the Δ-product-depth monotone formula complexity of ColIso_{F_{b,Δ+1}} is Θ(n^Δ) by Theorem 1 and the treedepth lower bound. This is off by one. F_{b,Δ+1} has treedepth Δ+1. As the paper itself notes in Section 3, any BET of cost c can be converted to an elimination tree of cost c, so λ_Δ(F_{b,Δ+1}) ≥ Δ+1. The natural elimination tree has product depth Δ and cost Δ+1, so λ_Δ(F_{b,Δ+1}) = Δ+1. Therefore Theorem 1 gives Θ(n^{Δ+1}), not Θ(n^Δ). Consequently, the derivation of Theorem 2 is incorrect; the claimed Ω(N^{Δ/2}) lower bound happens to remain true, but the stated Θ(n^Δ) and the 'almost-optimal' claim are not supported.
  3. [Section 6, Theorem 4] The proof of Theorem 4 asserts that ColIso_{F_{b,Δ+1}} has O(n^Δ)-size monotone formulas of product depth Δ. This repeats the same off-by-one: the correct upper bound is O(n^{Δ+1}). With this correction, the claimed lower bound Ω(n^{b+Δ}) for product depth Δ−1 does not imply Ω(s(N)^k) for s(N) of order n^{Δ+1} (or n^Δ), because (b+Δ)/(Δ+1) = k − (k−1)/(Δ+1) < k. Thus Theorem 4's depth hierarchy is not established by the given construction. The family or the parameter b must be reworked, or the theorem statement weakened.
minor comments (4)
  1. [Section 4, lower bound] The sentence 'Assume without loss of generality that 1,...,d are the vertices of H appearing in g and its ancestors' should be phrased as 'at least these vertices' or 'the first d vertices on that path', because the path chosen may contain more than d vertices. The argument still works, but the current wording is imprecise.
  2. [Section 3, Example 1] The example gives an O(n^4) formula of product depth two for P7, but a smaller O(n^3) formula of product depth two exists via the standard elimination tree of P7. This is not an error, but the example may mislead readers about the optimality of the construction.
  3. [Section 5, Remark 2] The remark claims optimality 'up to constant factors independent of Δ in the exponent of n'. Even after correcting the formula complexity to n^{Δ+1}, the gap between the circuit upper bound O(n^2) and the formula lower bound n^{Δ+1} is a factor of Δ+1 in the exponent, not a constant independent of Δ. The wording should be revised.
  4. [Section 3, Definition 7] The definition of product depth counts internal nodes even if their bag contains only pendant vertices. This is a valid choice, but it interacts subtly with the off-by-one issues in Sections 5–6; the paper would benefit from an explicit example showing the product depth of the natural elimination tree of F_{b,Δ+1}.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: λ_Δ(H) is a structural tree parameter and both bounds are genuine reductions; the Def. 7 'iff' inconsistency is a correctness issue, not circularity.

full rationale

The central parameter λ_Δ(H) is defined in Section 3 as the minimum over baggy elimination trees of the maximum root-to-leaf cost, where cost is a sum of bag sizes and product depth is a separate syntactic measure of the tree. This is a graph-structural definition, not a disguised formula-size exponent. The upper bound in Section 4 constructs a formula from an optimal baggy elimination tree and verifies correctness by induction, while the lower bound starts with an arbitrary formula, lifts LCAs to form a baggy elimination tree, bounds its product depth, and then counts how many monomials can share a gate. These are substantive combinatorial reductions rather than definitional identities: the upper bound must show all edge monomials are produced and no spurious monomials are introduced, and the lower bound must show that the lifted tree is valid and that its maximum-cost path controls the number of preimages per gate. The proof never fits a parameter to the target complexity and then renames it as a prediction. The citations to the authors' earlier work [7] provide definitions, the polynomial equivalence lemma, and the general LCA-lifting strategy, but they are not used as evidence for the new characterization itself; [7] is a published, parameter-free prior result that does not assume the bounded-depth formula result proved here. No uniqueness theorem is imported, and no ansatz is smuggled in by citation. The main remaining issue is Definition 7, which prints 'if and only if' for the bag-comparability condition: Example 1's root bag {2,4,6} contains non-adjacent vertices, and the upper and lower proof directions only use the forward direction (edges imply same or ancestor-descendant bags). Under the literal 'iff', λ_Δ would be a different parameter. This is an internal-consistency/correctness defect that should be repaired, but it does not make the derivation circular.

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

The paper's main theorem is self-contained in the sense that it uses no fitted constants or data-dependent parameters. The load-bearing unproved inputs are standard parse-tree facts, the cited ColIso–Hom equivalence, and the standing connectedness/fixed-H assumption. The main new entity, the baggy elimination tree, is a mathematical definition rather than an empirical postulate.

assumptions (3)
  • standard math Arithmetic formulas have standard parse-tree properties: for a monomial, a parse tree includes all children of multiplication gates and exactly one child of addition gates; replacing subtrees at shared multiplication gates yields another valid parse tree.
    Used throughout the lower-bound proof in Section 4 to construct a baggy elimination tree from a parse tree and to argue the mixed-assignment contradiction.
  • domain assumption Colored isomorphism polynomial ColIso_H is equivalent to the homomorphism polynomial Hom_H (Lemma 15 of [7]).
    The paper states the main theorems for ColIso_H but the abstract presents them for homomorphism polynomials; the transfer relies on this cited lemma.
  • domain assumption The pattern graph H is fixed, connected, and has more than one edge.
    Stated at the end of Section 2; connectedness is used in the root-bag argument of the lower-bound proof, and fixedness absorbs H-dependent constants into O(·).
invented entities (3)
  • Baggy elimination tree (BET)
    purpose: A rooted tree with vertex bags that generalizes elimination trees; its cost at bounded product depth is used to characterize monotone formula complexity.
    A new mathematical object introduced by this paper. Its validity is supported by the proof of Theorem 1, not by any external empirical handle.
  • λ_Δ(H), the minimum BET cost at product depth Δ
    purpose: The graph parameter claimed to equal the exponent of monotone bounded-depth formula size for ColIso_H.
    Defined to mirror formula-size exponents; the non-trivial content is the two-way proof in Section 4, but the parameter itself has no independent empirical support.
  • Core and non-core leaves of a BET
    purpose: Distinguishing leaves that contain a non-pendant vertex from leaves containing only pendant vertices; used to align product depth of the tree with product depth of the formula.
    A definitional device introduced in Definition 7 to make the elimination-tree product depth match formula product depth.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials." pith.science (2026). https://pith.science/paper/6TS4V5ZL

@misc{pith2026251103388,
  author       = {Pith},
  title        = {Pith review of: Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6TS4V5ZL}},
  note         = {Machine review of arXiv:2511.03388}
}
abstract

We introduce baggy elimination trees, a novel graph decomposition that generalises the classical elimination trees underlying treedepth, and use them to give a complete characterisation of the monotone bounded-depth formula complexity of graph homomorphism and coloured isomorphism polynomials. Specifically, we prove that the $\Delta$-product depth monotone formula complexity of these polynomials is $\Theta\!\left(n^{\lambda_\Delta(H)}\right)$, where $\lambda_\Delta(H)$ is the minimum cost of a baggy elimination tree for $H$ at BET-depth~$\Delta$. This result closes the last open case in the programme initiated by Komarath, Pandey and Rahul and continued by Bhargav, Chen, Curticapean and Dwivedi: tight size characterisations of monotone circuit complexity (via treewidth / bounded-depth treewidth), monotone ABP complexity (via pathwidth / bounded-depth pathwidth), and monotone formula complexity (via treedepth) were already known; our theorem supplies the missing bounded-depth formula characterisation via the new notion of bounded-depth baggy-elimination-tree cost $\lambda_\Delta$, completing the picture for all three models in algebraic complexity and their fixed depth variants. As applications, for constant-degree polynomial families we derive an almost-optimal separation between monotone circuits and monotone formulas at every fixed product depth: there exists a family computable by $O(N)$-size monotone circuits of product depth $\Delta$ that requires $\Omega(N^{\Delta/2})$-size monotone formulas of the same depth (and this exponent is optimal up to a constant factor). We also prove a strict depth hierarchy: for every $\Delta \geq 1$ and every constant $k \geq 2$, there is a constant-degree family with $O(s(N))$-size monotone formulas of product depth $\Delta$ that requires $\Omega(s(N)^k)$-size monotone formulas of product depth $\Delta - 1$.

Figures

Figures reproduced from arXiv: 2511.03388 by the authors.

Figure 1
Figure 1. Baggy elimination tree of product depth two for [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Parse tree to baggy elimination tree for [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

7 extracted references · 1 canonical work pages

  1. [7]

    Monotone Arithmetic Com- plexity of Graph Homomorphism Polynomials

    Balagopal Komarath, Anurag Pandey, and C. S. Rahul. “Monotone Arithmetic Com- plexity of Graph Homomorphism Polynomials”. In:Algorithmica85.9 (2023), pp. 2554– 2579. 10

    2023

  2. [1]

    C. S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi.Monotone Bounded-Depth Complexity of Homomorphism Polynomials. arXiv preprint arXiv:2505.22894. 2025. 9

    arXiv 2025

  3. [2]

    Robustly Sepa- rating the Arithmetic Monotone Hierarchy via Graph Inner-Product

    Arkadev Chattopadhyay, Utsab Ghosal, and Partha Mukhopadhyay. “Robustly Sepa- rating the Arithmetic Monotone Hierarchy via Graph Inner-Product”. In:42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Vol. 250. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibni...

    work page doi:10.4230/lipics.fsttcs.2022.12 2022

  4. [3]

    Homomorphism Tensors and Linear Equations

    Radu Curticapean. “Homomorphism Tensors and Linear Equations”. In:56th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015. 2015, pp. 326–339

    2015

  5. [4]

    Completeness for VP and VNP from Graph Homomorphism

    Arnaud Durand, Meena Mahajan, Guillaume Malod, and Nitin Saurabh. “Completeness for VP and VNP from Graph Homomorphism”. In:40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015. 2015, pp. 308–319

    2015

  6. [5]

    Graph Homomorphism and Natural VNP-Complete Families

    Prateek Dwivedi and Nitin Saxena. “Graph Homomorphism and Natural VNP-Complete Families”. In:Theory Comput. Syst.62.2 (2018), pp. 441–464

    2018

  7. [6]

    On monotone formulae with restricted depth

    Maria Klawe, Wolfgang J. Paul, Nicholas Pippenger, and Mihalis Yannakakis. “On monotone formulae with restricted depth”. In:Proceedings of the sixteenth annual ACM symposium on Theory of computing (STOC ’84). New York, NY, USA: Association for Computing Machinery, 1984, pp. 480–487.doi:10.1145/800057.808717

    arXiv 1984

Pith tools

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