We study sparse polynomials with bounded individual degree and the class of their factors. In particular we obtain the following algorithmic and structural results:

1. A deterministic polynomial-time algorithm for finding all the sparse divisors of a sparse polynomial with bounded individual degree. As part of this, we establish ... more >>>

A symbolic determinant under rank-one restriction computes a polynomial of the form $\det(A_0 + A_1y_1 + \ldots + A_ny_n)$, where $A_0, A_1, \ldots, A_n$ are square matrices over a field $\mathbb{F}$ and $\rank(A_i) = 1$ for each $i \in [n]$. This class of polynomials has been studied extensively, since the ... more >>>

We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the ... more >>>