We say that a polynomial f(x_1,\ldots,x_n) is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

Fix a prime p. Given a positive integer k, a vector of positive integers {\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k) and a function \Gamma: \mathbb{F}_p^k \to \F_p, we say that a function P: \mathbb{F}_p^n \to \mathbb{F}_p is (k,{\bf \Delta},\Gamma)-structured if there exist polynomials P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p ... more >>>

In continuation to our recent work on noncommutative
polynomial factorization, we consider the factorization problem for
matrices of polynomials and show the following results.
\begin{itemize}
\item Given as input a full rank d\times d matrix M whose entries
M_{ij} are polynomials in the free noncommutative ring
more >>>

For every constant d, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial f given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of f of degree at most d together with their respective multiplicities. Moreover, ... 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 >>>