Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds

Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, obstructing the use of greatest common divisors. Fix a prime $p \in \mathbb{Z}$ and $f \in ( \mathbb{Z}/p^n \mathbb{Z} ) [x]$ any nonzero polynomial of degree $d$ whose coefficients are not all divisible by $p$. For the case $n=2$, we prove a new efficient algorithm to count the roots of ...

In this paper we are interested in the following problem. Let $p$ be a prime number, $S\subset \F_p$ and $\cP\subset \{P\in\F_p [X]:\deg P\le d\}$. What is the largest integer $k$ such that for all subsets $\cA, \cB$ of $\F_p$ satisfying $\cA\cap\cB =\emptyset$ and $|\cA\cup\cB |=k$, there exists $P\in\cP$ such that $P(x)\in S$ if $x\in\cA$ and $P(x)\not\in S$ if $x\in\cB$? This problem corresponds to the study of the complexity of some families of pseudo-random subsets. Firs...

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as $$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$ where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = d$. In this paper, we give a $\text{poly}((ns)^t)$-time learning algorithm for finding the $Q_i$'s given (black-box access to) $f$, if the $Q_i's$ satisfy certain non-deg...

We discuss the problem of constructing a small subset of a finite field containing primitive elements of the field. Given a finite field, $\mathbb{F}_{q^n}$, small $q$ and large $n$, we show that the set of all low degree polynomials contains the expected number of primitive elements. The main theorem we prove is a bound for character sums over short intervals in function fields. Our result is unconditional and slightly better than what is known (conditionally under GRH) in...

These are the notes of my lectures at the 1996 European Congress of Mathematicians. {} Polynomials appear in mathematics frequently, and we all know from experience that low degree polynomials are easier to deal with than high degree ones. It is, however, not clear that there is a well defined class of "low degree" polynomials. For many questions, polynomials behave well if their degree is low enough, but the precise bound on the degree depends on the concrete problem. {} It ...

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach t...

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes $\widetilde{O}(n^{3/2}\log q + n \log^2 q)$ time to factor polynomials of degree $n$ over the finite field $\mathbb{F}_q$ with $q$ elements. A significant open problem is if the $3/2$ exponent can be improved. We study a collection of algebraic problems and establish a web...

In this paper we characterize the set of polynomials $f\in\mathbb F_q[X]$ satisfying the following property: there exists a positive integer $d$ such that for any positive integer $\ell$ less or equal than the degree of $f$, there exists $t_0$ in $\mathbb F_{q^d}$ such that the polynomial $f-t_0$ has an irreducible factor of degree $\ell$ over $\mathbb F_{q^d}[X]$. This result is then used to progress in the last step which is needed to remove the heuristic from one of the qu...

Let $p$ be a prime. Given a polynomial in $\F_{p^m}[x]$ of degree $d$ over the finite field $\F_{p^m}$, one can view it as a map from $\F_{p^m}$ to $\F_{p^m}$, and examine the image of this map, also known as the value set. In this paper, we present the first non-trivial algorithm and the first complexity result on computing the cardinality of this value set. We show an elementary connection between this cardinality and the number of points on a family of varieties in affine ...

We obtain new upper bounds on the number of distinct roots of lacunary polynomials over finite fields. Our focus will be on polynomials for which there is a large gap between consecutive exponents in the monomial expansion.