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

Polynomial representations of Boolean functions over various rings such as $\mathbb{Z}$ and $\mathbb{Z}_m$ have been studied since Minsky and Papert (1969). From then on, they have been employed in a large variety of fields including communication complexity, circuit complexity, learning theory, coding theory and so on. For any integer $m\ge2$, each Boolean function has a unique multilinear polynomial representation over ring $\mathbb Z_m$. The degree of such polynomial is ca...

An open problem in complexity theory is to find the minimal degree of a polynomial representing the $n$-bit OR function modulo composite $m$. This problem is related to understanding the power of circuits with $\text{MOD}_m$ gates where $m$ is composite. The OR function is of particular interest because it is the simplest function not amenable to bounds from communication complexity. Tardos and Barrington established a lower bound of $\Omega((\log n)^{O_m(1)})$, and Barringto...

Suppose $k,p\!\in\!\mathbb{N}$ with $p$ prime and $f\!\in\!\mathbb{Z}[x]$ is a univariate polynomial with degree $d$ and all coefficients having absolute value less than $p^k$. We give a Las Vegas randomized algorithm that computes the number of roots of $f$ in $\mathbb{Z}/\!\left(p^k\right)$ within time $d^3(k\log p)^{2+o(1)}$. (We in fact prove a more intricate complexity bound that is slightly better.) The best previous general algorithm had (deterministic) complexity expo...

In this paper, we concentrate on counting and testing dominant polynomials with integer coefficients. A polynomial is called dominant if it has a simple root whose modulus is strictly greater than the moduli of its remaining roots. In particular, our results imply that the probability that the dominant root assumption holds for a random monic polynomial with integer coefficients tends to 1 in some setting. However, for arbitrary integer polynomials it does not tend to 1. For ...

The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between polynomial degree and quantum query complexit...

We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomials $f$, given an oracle access to $f(x)^e$ for $x\in\mathbb F_q$, where $\mathbb F_q$ is the finite field of $q$ elements and an extension fields access is not permitted. The naive interpolation algorithm needs $de+1$ queries, where $d =\max\{{\rm deg}\ f, {\rm deg }\ g\}$ and thus requires $ de<q$. For a prime $q = p$, we design an algorithm that is asymptotical...

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bo...

We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions $f:\{1, ..., N\}\to\{1, ..., M\}$, its polynomial degree is the same for all $M\geq N$. Therefore, if we have a quantum lower bound for some (possibly, quite large) range $M$ which is shown using polynomials method, we immediately get the same lower bound for all ranges $M\geq N$. In particular, we get $\Omega(N^{1/3})$ ...

We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree <q, has a root in F_q. A corollary of our method --- the first with complexity sub-linear in q when t is fixed --- is that the nonzero roots in F_q can be partitioned into at most 2 \sqrt{t-1} (q-1)^{(t-2)(t-1)} cosets of two subgroups S_1,S_2 of F^*_q, with S_1 in S_2. Another corollary is the first deterministic sub-linear algo...

We investigate the problem of showing that the values of a given polynomial are smooth (i.e., have no large prime factors) a positive proportion of the time. Although some results exist that bound the number of smooth values of a polynomial from above, a corresponding lower bound of the correct order of magnitude has hitherto been established only in a few special cases. The purpose of this paper is to provide such a lower bound for an arbitrary polynomial. Various generaliza...