{"id":"1c2bdb2c-5b9f-48c4-869d-e1407dafb66d","arxiv_id":"2505.22894","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Monotone product-depth Δ circuits for homomorphism polynomials of pattern H have size Θ(n^{ptw_Δ(H)+1}), where ptw_Δ is the pruned bounded-depth treewidth introduced here.","lead":"This paper shows that the number of multiplication layers allowed in a monotone circuit forces a precise exponent in the circuit size needed to compute homomorphism and colorful subgraph polynomials, governed by a new graph measure called pruned Δ-treewidth. It also proves a depth hierarchy: some polynomials need far larger circuits when the allowed depth drops by one, and the trade-off is optimal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 is false as stated for stars: for H=K_{1,3}, H†=K1 has tw=0, so the theorem predicts O(n) size, but the polynomial depends on n^2 variables and the proof's own construction gives Ω(n^2).","rationale":"The reader's weakest assumption was Claim 5.2, the extraction of a bounded-height tree-decomposition from parse trees. That concern is about the lower-bound proof. My objection is more fundamental and concerns the upper bound and the theorem statement itself: Theorem 1.2 fails for graphs whose pruned core has treewidth 0, such as stars. For K_{1,3}, the polynomial contains all n^2 variables, forcing Ω(n^2) size, while ptw_Δ(H)=0 predicts O(n). The paper's own construction in Section 4 yields the correct O(n^2) via Lemma 4.1, so the proof and statement are internally inconsistent. This invalidates the central exact-exponent claim. The Theorem 6.1 size-bound error noted by the reader is real but secondary; even if fixed, the main theorem remains false as stated unless an additional hypothesis (e.g., H† has treewidth at least 1, or exponent max(ptw_Δ(H)+1,2)) is added. For these reasons the current version should be rejected, though a repaired version may hold under suitable restrictions.","tokens_in":17333,"tokens_out":40195,"duration_ms":489848,"concrete_test":"Check Theorem 1.2 on H = K_{1,3} with Δ=2. Compute the set of variables appearing in Hom_{H,n}: it is {x_{i,j} : i,j ∈ [n]}, of size n^2, so any circuit has at least n^2 input leaves. Independently, apply Lemma 4.1 to the tree-decomposition constructed in Section 4 for this H: the decomposition has a root bag {center} and leaves {center, leaf_l}, so max bag size is 2, yielding O(n^2) gates, not the claimed O(n^{ptw+1}) = O(n). Either computation falsifies the upper bound in Theorem 1.2.","verdict_should_be":"REJECT","load_bearing_attack":"Let H be the star K_{1,3}. Since H† is obtained by removing all degree-1 vertices, H† is K1, so tw_Δ(H†)=0 and ptw_Δ(H)=0 for every Δ. Theorem 1.2 therefore claims monotone circuits of size O(n^{ptw_Δ(H)+1}) = O(n) and product-depth Δ for Hom_{H,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}. Under Definition 2.1, circuit size counts vertices, so any circuit has at least n^2 input gates, giving Ω(n^2). The same conclusion follows from the cited KPR23 result, which gives Θ(n^{tw(H)+1}) = Θ(n^2) for tw(K_{1,3})=1. The internal proof in Section 4 also exposes the gap: augmenting a width-0 tree-decomposition of H†=K1 with leaf bags {center, leaf} produces a tree-decomposition of H with maximum bag size 2, so Lemma 4.1 yields O(n^2), not O(n^{ptw+1}) = O(n). The error is that degree-1 leaves force bag size at least 2 and hence a factor n^2 whenever H† has treewidth 0; the claimed safe removal of degree-1 vertices is only safe for the exponent when tw_Δ(H†) ≥ 1. Thus the exact exponent characterization in Theorem 1.2 is false as stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17648,"tokens_out":17675,"duration_ms":187798,"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":[{"comment":"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":"Theorem 1.2 / Definition 3.2"},{"comment":"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.","section":"Section 4, upper-bound proof after Lemma 4.1"},{"comment":"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.","section":"Theorem 5.3 / Section 5.2"},{"comment":"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.","section":"Theorem 6.1 / Theorem 1.4"}],"minor_comments":[{"comment":"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.","section":"Section 4"},{"comment":"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":"Figure 1"},{"comment":"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.","section":"Section 3.1"},{"comment":"The condition Δ≥|E(H)| is stated but its role in the lower-bound proof is never discussed; please indicate where this condition is used.","section":"Theorem 1.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is technically interesting and the repair of the central error appears localized to the treatment of degree-1 vertices and to the exponent calculation in the hierarchy theorem. However, the current version contains an elementary counterexample to the main theorem, so the authors should restate the pruned parameter appropriately (for graphs with at least one edge, the exponent appears to need an extra +1 at ptw_Δ=0), re-prove the affected upper and lower bounds, and correct the hierarchy theorem's exponent before the paper can be considered further."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nNow 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.\n\nBottom 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.","headline":"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.","tokens_in":18238,"tokens_out":8386,"would_cite":false,"duration_ms":87689,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new graph parameter, pruned $\\Delta$-treewidth, exactly sets the exponent of bounded-depth monotone circuits for homomorphism polynomials.","keywords":["monotone circuits","bounded-depth circuits","homomorphism polynomials","treewidth","tree-decomposition","algebraic complexity","depth hierarchy","graph polynomials"],"falsifier":"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.","tokens_in":17101,"feed_emoji":"🌳","tokens_out":15882,"duration_ms":161922,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bounded-depth circuit size equals pruned Δ-treewidth plus one","feed_subtitle":"Homomorphism and colorful subgraph polynomials need exactly n^(ptwΔ(H)+1) gates at product-depth Δ.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the previous tight monotone complexity result for these polynomials and the Hom/ColSub transfer lemma that the proof adapts to bounded depth.","marker":"[KPR23]"},{"why":"Provides the earlier near-optimal depth-hierarchy lower bound for small product-depth that the new hierarchy theorem strengthens to an optimal, all-depth bound.","marker":"[Chi+18]"},{"why":"One of the original sources of the parse-tree technique that the lower-bound proof uses to extract tree-decompositions from circuits.","marker":"[JS82]"}],"fun_headline_variants":["Monotone depth-Δ circuit size = n^(pruned treewidth + 1)","Pruned treewidth sets exact size for depth-Δ monotone circuits","Optimal depth hierarchy: monotone circuits need pruned Δ-treewidth","Exact size for depth-Δ monotone homomorphism circuits","Depth-Δ monotone circuits need n^(pruned treewidth+1) gates exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Monotone depth-Δ circuit size = n^(pruned treewidth + 1)","Pruned treewidth sets exact size for depth-Δ monotone circuits","Optimal depth hierarchy: monotone circuits need pruned Δ-treewidth","Exact size for depth-Δ monotone homomorphism circuits","Depth-Δ monotone circuits need n^(pruned treewidth+1) gates exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001013,"raw_usage":{"total_tokens":4394,"prompt_tokens":1178,"completion_tokens":3216,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":794,"completion_tokens_details":{"reasoning_tokens":3114}},"tokens_in":794,"tokens_out":3216,"duration_ms":25834,"temperature":1.0,"reasoning_tokens":3114,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:01:49.097238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}