On the Complexity of Solving Bivariate Systems
summary
Algorithm computes a squarefree eliminant and rational parametrization for two bivariate polynomials with integer coefficients in near-optimal bit complexity ≈ d^4 up to d^ε, using a Monte Carlo scheme. It combines symbolic Newton lifting (p-adic/power lifting of solutions), fast modular composition from recent modular-composition results to reduce evaluation cost, and deflation for multiple roots. Over coefficient fields the algebraic case remains worse (running time around d^{ω+7/2} using polynomial matrix multiplication), but the integer/boolean method meets the stated target.
AI-written summary · about