Multivariate Resultants: Complexity and Applications for ETR

The multivariate (or Macaulay) resultant is a polynomial in the coefficients of n homogeneous polynomials in n complex variables that vanishes precisely when these polynomials have a nonzero common root. This property makes it a fundamental object in computational algebra. A recent breakthrough showed that multivariate resultants can be computed in the counting hierarchy [AGS26], but the known hardness results only yield NP-hardness [GKP13]. We significantly narrow down the complexity of multivariate resultants by proving three results. First, polynomial-size arithmetic circuits for multivariate resultants imply that VP equals VNP. Second, evaluating resultants modulo powers of two is #P-hard, and deciding an addressed bit of their absolute value is PP-hard, under polynomial-time Turing reductions. Third, deciding the sign of a resultant is parity-P-hard, even when it is guaranteed to be nonzero. The hardness results hold even for the resultants of homogeneous quadratic forms defined by symmetric tensors of order three. Such resultants are also known as tensor determinants or symmetric hyperdeterminants. The circuit lower bound also applies to discriminants of cubic forms. For integer symmetric cubic tensors, evaluation modulo two to the power k, with k supplied in unary, is complete for FP with a PP oracle under polynomial-time Turing reductions. The addressed-bit hardness holds even when the bit position is supplied in unary; the reduction uses polynomially many queries at varying positions. The same upper bound for general resultants remains open. Our circuit and modular-evaluation hardness proofs identify nonzero monomial coefficients of shifted tensor determinants. Elementary resultant identities show that the coefficient of every connected monomial in which each index occurs exactly three times is nonzero. A parity construction extracts a hard grid pattern by a difference of two evaluations. We also apply resultants to real feasibility, proving that the existential theory of the reals belongs to the counting hierarchy. The proof extends the resultant-sign construction used for parity-P-hardness to detect real solutions through conjunctions of polynomial inequalities. Combining short derivative-sign descriptions of roots with a finite family of projections reduces real feasibility to resultant computations covered by the counting-hierarchy algorithms of Andrews, Garg, and Schost [AGS26].