Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given by an arithmetic circuit $C$ of size $s$. Given $C$ as the input, is there a deterministic algorithm to check whether all the irreducible factors of $f$ in $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ are linear forms? On a related note, given a linear form $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$, can we check deterministically whether $l$ is factor of $f$. Of course, we want running time to be polynomial in both the cases. By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.

  • $\begingroup$ When you say "size $s$" does that mean number of gates/wires, or total bit-size (taking into account the bits used to describe any constants in the circuit)? $\endgroup$ Jun 3 '14 at 16:16
  • $\begingroup$ @JoshuaGrochow, yeah size is the toal bit size here. $\endgroup$ Jun 3 '14 at 17:31
  • 2
    $\begingroup$ Three comments you probably already have in mind, but just in case: 1. Concerning polynomial time, factorization algorithms for arithmetic circuits are polynomial in the size and the degree of the polynomial, and I am not aware of algorithms for related tasks that run in time polynomial in the size only. 2. Concerning determinism, these algorithms are randomized and deterministic variants become exponential in the number of variables. 3. The second question can be translated into a PIT problem, so your question amounts to derandomize some specific PIT algorithm. $\endgroup$
    – Bruno
    Jun 4 '14 at 9:13
  • $\begingroup$ I also add that I find these problems very interesting and I'd like to know what is already known on this! $\endgroup$
    – Bruno
    Jun 4 '14 at 9:15
  • $\begingroup$ re PIT, polynomial identity testing via Schwartz–Zippel / wikipedia & there is much active research in that area. (re that pg PIT can be used to factor integers but what is a ref that outlines how to use it to factor polynomials?) $\endgroup$
    – vzn
    Jun 4 '14 at 22:34

As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of Kaltofen (PDF) which actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for general circuits was recently shown by Kopparty, Saraf and Shpilka to be equivalent to the problem of blackbox-PIT for general circuits.

As mentioned by Bruno, if you are interested in checking a the given circuit is divisible by a given $\ell$, then this reduces to a specific PIT problem. We don't know how to do this deterministically in general but I know of one special case where we know how to do this PIT. There is a deterministic poly-time algorithm (PDF) to check if a given $\ell$ divides a given sparse polynomial $f$.

(Another trivial special case when $f$ is given by a bounded top fan-in depth three circuit. There, $f \bmod \ell$ is also a bounded fan-in depth three circuit and we know how to do PIT in deterministic polynomial time.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.