Metraipolis › archive › dc_8dfa556881eb

Some algebraic and geometric computations in CH via Chow forms — arXiv:2611.05289

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05289
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:52.497Z
SHA-256 of the archived text
178fe0aa7e30a8772f68d9889716e5aa1fb5086c9adf44c7378c9fef9fb719bc
Stable URL of this page
https://metraipolis.com/documento/dc_8dfa556881eb

How to cite

Some algebraic and geometric computations in CH via Chow forms — arXiv:2611.05289 — arXiv (en), https://arxiv.org/abs/2611.05289 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8dfa556881eb (Metraipolis archive dc_8dfa556881eb, sha256 178fe0aa7e30a8772f68d9889716e5aa1fb5086c9adf44c7378c9fef9fb719bc)
BibTeX
@misc{dc8dfa556881eb,
  title = {Some algebraic and geometric computations in CH via Chow forms — arXiv:2611.05289},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05289},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8dfa556881eb; sha256 178fe0aa7e30a8772f68d9889716e5aa1fb5086c9adf44c7378c9fef9fb719bc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05289. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Symbolic Computation (cs.SC).
Pagina del lavoro: https://arxiv.org/abs/2611.05289 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:41:25.369Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).