Amiel Ferman

The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrm{AC}^0$

We prove that the complete extended Euclidean scheme for pairs of monic univariate polynomials over a field of characteristic zero cannot be computed by polynomial-size, constant-depth piecewise arithmetic circuits in the select-gate model of Andrews and Wigderson. In fact, the lower bound already holds for the simpler...