REVIEW
Some algebraic and geometric computations in CH via Chow forms
Computational Complexity · Submitted 3 Nov 2026 · 300 references
Pith's verdict: Real new upper bounds (PSPACE to CH) for Chow-form and equidimensional-component problems, built on a coherent reduction to resultants; the one real gap is a uniformity proof that is delegated rather than written out, and it is fixable rather than fatal.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The paper claims a single polylogtime-uniform family of constant-depth threshold circuits computes the Chow forms of every equidimensional component, dropping decomposition, membership, and degree problems from PSPACE to the counting…
The reading
What carries the argument
The central objects are the Chow form and the geometric resolution. The Chow form of an equidimensional projective variety of dimension $k$ is the unique (up to scaling) polynomial in the coefficients of $k+1$ linear forms that vanishes exactly when those linear forms have a common zero on the variety; it encodes the variety as a single polynomial. A geometric resolution is a parametric description of an affine variety: a hypersurface $q$ together with rational functions $r_j/q'$ that parametrize a dense open subset of the variety. The argument is carried by two mechanisms. First, for each dimension $k$, the paper forms the deformed system $(1-t)G_i + t x^{d_i}$, takes the trailing term in $t$ of its resultant with $k+1$ generic linear forms, and shows that this trailing term is, up to squarefree part, the Chow form of a limit subvariety that contains the $k$-dimensional component of $V(F_1,\dots,F_m)$; this generalizes the classical generalized-characteristic-polynomial construction from isolated points to all dimensions. Second, because any excess component must lie inside a higher-dimensional component, the paper computes all these over-varieties in parallel and prunes them simultaneously—each $W_k$ is trimmed, through a GCD computation on geometric resolutions derived from its Chow form, against $W_{k+1}\cup\cdots\cup W_r$—and lifts the pruned resolution back to the true Chow form via a factor-lifting circuit. All heavy polynomial arithmetic (resultants, GCDs, squarefree parts, interpolation, factor lifting) is implemented by previously built polylogtime-uniform constant-depth threshold circuits, and the paper's Lemmas 2.20 and 2.22 convert such uniform circuit families into CH membership for their languages.
Extended reading notes
Core claim
The paper's central claim is Theorem 4.9: there exists a polylogtime-uniform family of constant-depth threshold circuits, indexed by the number of variables and the degrees of the input forms, which takes dense forms $F_1,\dots,F_m \in \mathbb{Q}[x_0,\dots,x_n]$ together with a string of random integers, and with high probability outputs integer multiples of the Chow forms of all equidimensional components of $V(F_1,\dots,F_m)$. The Chow form of a $k$-dimensional component is the single polynomial in auxiliary linear-form coefficients whose vanishing records exactly which $(k+1)$-tuples of hyperplanes meet that component, so the circuit family is a complete encoding of the decomposition. Since the family is polylogtime-uniform and constant-depth, the simulation lemmas convert it into CH membership for the associated languages, and the paper derives from it the announced results: CH decision procedures for Chow-form zeros and monomial support, for membership in a given equidimensional component, and for membership in the closure of the image of an irreducible variety under a polynomial map; $\mathrm{FP}^{\mathrm{CH}}$ computation of component degrees; and CH decision of approximate polynomial satisfiability over the larger field families. The proof has two stages: first, a deformation of the defining equations, read off from the trailing term of a perturbed resultant, produces for each $k$ an equidimensional over-variety $W_k \subseteq V$ containing the $k$-dimensional component; then, because any excess component must lie in a higher-dimensional component, a parallel pruning step using geometric resolutions and GCD computations removes them, and factor-lifting recovers the exact Chow form.
Load-bearing premise
The load-bearing premise is that the exponential-size, constant-depth threshold circuit family $\mathcal{C}_{\mathrm{CHOW}}$ of Theorem 4.9 is polylogtime-uniform: the paper asserts at the end of the proof that uniformity follows from the uniformity of the subcircuits and even remarks that uniformity proofs are kept terse for readability, but it does not exhibit the direct connection language, and if that uniformity fails, the lemmas that simulate the family inside CH (Lemmas 2.20 and 2.22) no longer apply and the collapse of the decision problems to CH is unsupported.
Editorial extensions
If this is right
- Zero tests and monomial-support tests for the Chow form of the $k$-th equidimensional component are decidable in CH (Theorems 1.1 and 1.2).
- The degree of each equidimensional component—and therefore of the whole variety, and the number of its isolated points—is computable in $\mathrm{FP}^{\mathrm{CH}}$, improving the prior FPSPACE bound (Theorem 1.4).
- Membership of a given rational point in the dimension-$k$ equidimensional component of a variety is decidable in CH, improving the prior PSPACE bound (Theorem 1.5).
- Membership in the closure of the image of an irreducible variety under a polynomial map is decidable in CH (Theorem 1.6), and the approximate polynomial satisfiability problem is in CH over finite fields, rational-function fields, and number fields (Theorem 1.9).
- All of these statements rest on a single randomized circuit construction: the output is guaranteed to be a correct $\mathbb{Z}$-multiple of the Chow forms with high probability over the random inputs, so the algorithms inherit explicit probability bounds from Theorem 4.9.
Reading between the lines
- If Theorem 4.9 holds, the same circuit skeleton—uniform constant-depth resultant circuits plus geometric resolutions—is a natural template for attacking the remaining PSPACE-level elimination problems, most directly irreducible-component decomposition, since the paper stops at equidimensional components and its factor-lifting step is already a constant-depth subroutine.
- The randomized element of the construction looks derandomizable in principle: the failure probability in Theorem 4.9 is polynomial-quality, so under a standard hitting-set or hardness assumption one would expect a deterministic CH algorithm, with a concrete intermediate step being the replacement of the random change of coordinates by a small explicit candidate set.
- The trailing-term short-circuit used for APS over finite fields deliberately avoids multivariate GCDs, which suggests that 'is this coefficient zero' questions in elimination theory may be genuinely easier than full projection problems in positive characteristic; applying the same short-circuit to other coefficient-testing problems would test this.
- The circuit size is polynomial in $h,n,m$ and $(d+1)^{\mathrm{poly}(n)}$, slightly worse than the $d^{O(n)}$ size of earlier straight-line-program algorithms but at constant depth; whether the exponent can be reduced to $O(n)$ without losing constant depth is a concrete open comparison.
Original abstract
The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms. We improve the state-of-the-art complexity bounds from PSPACE to CH, the counting hierarchy, for a number of problems related to equidimensional decomposition, including deciding (1) whether the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety vanishes at a given point, (2) whether a given monomial is in the support of the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety, (3) membership in a given equidimensional component of a given algebraic variety, and (4) membership in the closure of the image of an irreducible variety under a polynomial map. As an application of our algorithm to decide membership in the closure of the image of a variety under a polynomial map, we show that the approximate polynomial satisfiability problem can be decided in CH. We also show that the degree of the $k^{\text{th}}$ equidimensional component of a given projective variety can be computed in $\text{FP}^{\text{CH}}$. Our main technical result is the construction of a polylogtime-uniform family of constant-depth, exponential-size threshold circuits that compute the Chow forms of the equidimensional components of a given projective variety. We construct these circuits by combining the machinery of geometric resolutions together with the uniform constant-depth, exponential-size threshold circuits of Andrews, Garg, and Schost (FOCS 2026) for the multivariate resultant.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms. We improve the state-of-the-art complexity bounds from PSPACE to CH, the counting hierarchy, for a number of problems related to equidimensional decomposition, including deciding (1) whether the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety vanishes at a given point, (2) whether a given monomial is in the support of the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety, (3) membership in a given equidimensional component of a given algebraic variety, and (4) membership in the closure of the image of an irreducible variety under a polynomial map. As an application of our algorithm to decide membership in the closure of the image of a variety under a polynomial map, we show that the approximate polynomial satisfiability problem can be decided in CH. We also show that the degree of the $k^{\text{th}}$ equidimensional component of a given projective variety can be computed in $\text{FP}^{\text{CH}}$. Our main technical result is the construction of a polylogtime-uniform family of constant-depth, exponential-size threshold circuits that compute the Chow forms of the equidimensional components of a given projective variety. We construct these circuits by combining the machinery of geometric resolutions together with the uniform constant-depth, exponential-size threshold circuits of Andrews, Garg, and Schost (FOCS 2026) for the multivariate resultant.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms. | contribution 0.98 | 0.71 | 0.06 | asserted 0.80 |
| s2 | We improve the state-of-the-art complexity bounds from PSPACE to CH, the counting hierarchy, for a number of problems related to equidimensional decomposition, including deciding (1) whether the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety vanishes at a given point, (2) whether a given monomial is in the support of the Chow form of the $k^{\text{th}}$ equidimensional component of a given projective variety, (3) membership in a given equidimensional component of a given algebraic variety, and (4) membership in the closure of the image of an irreducible variety under a polynomial map. | result 0.61 | 0.94 | 0.67 | asserted 1.00 |
| s3 | As an application of our algorithm to decide membership in the closure of the image of a variety under a polynomial map, we show that the approximate polynomial satisfiability problem can be decided in CH. | result 0.87 | 0.94 | 0.08 | asserted 1.00 |
| s4 | We also show that the degree of the $k^{\text{th}}$ equidimensional component of a given projective variety can be computed in $\text{FP}^{\text{CH}}$. | result 0.93 | 0.95 | 0.08 | asserted 1.00 |
| s5 | Our main technical result is the construction of a polylogtime-uniform family of constant-depth, exponential-size threshold circuits that compute the Chow forms of the equidimensional components of a given projective variety. | contribution 0.72 | 0.96 | 0.87 | asserted 1.00 |
| s6 | We construct these circuits by combining the machinery of geometric resolutions together with the uniform constant-depth, exponential-size threshold circuits of Andrews, Garg, and Schost (FOCS 2026) for the multivariate resultant. | method 0.99 | 0.91 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.