We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews \& Wigderson who showed such an upper bound over fields of zero ... more >>>
We show that algebraic formulas and constant-depth circuits are \emph{closed} under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas ... more >>>
We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree d over finite field \mathbb{F}_q. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time \tilde{O}(d^4 \log^4{q}).
Our construction extends Shoup's deterministic algorithm ... more >>>