Modular composition is the problem of computing the coefficient vector of the polynomial $f(g(x)) \bmod h(x)$, given as input the coefficient vectors of univariate polynomials $f$, $g$, and $h$ over an underlying field $\mathbb{F}$. While this problem is known to be solvable in nearly-linear time over finite fields due to work of Kedlaya & Umans, no such near-linear-time algorithms are known over infinite fields, with the fastest known algorithm being from a recent work of Neiger, Salvy, Schost & Villard that takes $O(n^{1.43})$ field operations on inputs of degree $n$. In this work, we show that for any infinite field $\mathbb{F}$, modular composition is in the border of algebraic circuits with division gates of nearly-linear size and polylogarithmic depth. Moreover, this circuit family can itself be constructed in near-linear time.

Our techniques also extend to other algebraic problems, most notably to the problem of computing greatest common divisors of univariate polynomials. We show that over any infinite field $\mathbb{F}$, the GCD of two univariate polynomials can be computed (piecewise) in the border sense by nearly-linear-size and polylogarithmic-depth algebraic circuits with division gates, where the circuits themselves can be constructed in near-linear time. While univariate polynomial GCD is known to be computable in near-linear time by the Knuth-Schönhage algorithm, or by constant-depth algebraic circuits from a recent result of Andrews & Wigderson, obtaining a parallel algorithm that simultaneously achieves polylogarithmic depth and near-linear work remains an open problem of great interest. Our result shows such an upper bound in the setting of border complexity.

An anonymous referee pointed out a gap in the proofs of Theorems 6.2 and 6.4. All the results in the paper crucially rely on the correctness of these
theorems.

Modular composition is the problem of computing the coefficient vector of the polynomial $f(g(x)) \bmod h(x)$, given as input the coefficient vectors of univariate polynomials $f$, $g$, and $h$ over an underlying field $\mathbb{F}$. While this problem is known to be solvable in nearly-linear time over finite fields due to work of Kedlaya & Umans, no such near-linear-time algorithms are known over infinite fields, with the fastest known algorithm being from a recent work of Neiger, Salvy, Schost & Villard that takes $O(n^{1.43})$ field operations on inputs of degree $n$. In this work, we show that for any infinite field $\mathbb{F}$, modular composition is in the border of algebraic circuits with division gates of nearly-linear size and polylogarithmic depth. Moreover, this circuit family can itself be constructed in near-linear time.

Our techniques also extend to other algebraic problems, most notably to the problem of computing greatest common divisors of univariate polynomials. We show that over any infinite field $\mathbb{F}$, the GCD of two univariate polynomials can be computed (piecewise) in the border sense by nearly-linear-size and polylogarithmic-depth algebraic circuits with division gates, where the circuits themselves can be constructed in near-linear time. While univariate polynomial GCD is known to be computable in near-linear time by the Knuth-Schönhage algorithm, or by constant-depth algebraic circuits from a recent result of Andrews & Wigderson, obtaining a parallel algorithm that simultaneously achieves polylogarithmic depth and near-linear work remains an open problem of great interest. Our result shows such an upper bound in the setting of border complexity.