13
$\begingroup$

Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with $d > 1$ by $x_i$. The result is obviously a multilinear polynomial.

Consider the following problem: given an arithmetic circuit $C(x_1,\ldots,x_n)$ over $F$ and given field elements $a_1,\ldots,a_n$, compute $\hat{C}(a_1,\ldots,a_n)$.

Question: Assuming field-arithmetic can be done in unit time, is there a polynomial-time algorithm for this? Added later: I would also be interested in the special case where $C$ is actually a formula (a circuit of fan-out $1$).

$\endgroup$
  • 1
    $\begingroup$ Why would it be equivalent to computing the output of a closed circuit? The problem I am facing is that the circuit can have disjoint paths from an input $x_i$ to several internal multiplication nodes, and evaluating each one of those internal multiplication nodes would require replacing $x_i$ by $a_i$ in one path and by $1$ in the other. In a circuit with an exponential number of paths, it looks like there is an exponential number of cases to take care of. $\endgroup$ – slimton Nov 11 '10 at 8:34
  • 2
    $\begingroup$ @Kaveh: I don't get it. Look at the circuit $(x * x)$. If you just replace the node of input $x$ by a node with value $a$ and evaluate in the standard way you end up returning $a^2$ instead of $a$. Model of computation: just normal polynomial time on Turing machines. Think of the field as being $Z/3Z$ for concreteness, if you want. $\endgroup$ – slimton Nov 11 '10 at 12:01
  • 2
    $\begingroup$ @Kaveh: I don't understand how such an algorithm implies what you say, but this does indeed contradict a common hypothesis in arithmetic circuit complexity: that the Permanent has no poly-sized arithmetic circuits (over fields other than F_2). Consider the polynomial $p=\prod_i(\sum_j x_{ij} y_j)$. The multilinear part $q$ of this polynomial has the property that its highest degree ($=2n$) part is just $r = y_1y_2\cdots y_n Per(x_{11},\ldots,x_{nn})$. If there is a small arithmetic circuit computing $q$, then one can show that there is a small arithmetic circuit computing $r$. $\endgroup$ – Srikanth Nov 12 '10 at 2:05
  • 1
    $\begingroup$ @Srikanth: I didn't see your comment before posting my answer (which turned out to be the same construction you gave in your comment). I have since deleted my answer, and you should post your comment as an answer. $\endgroup$ – Joshua Grochow Nov 13 '10 at 0:58
  • 2
    $\begingroup$ @Joshua: I have not added my comment as an answer since I don't understand why Kaveh's construction works. I see that the arithmetic circuit computes a polynomial that agrees with the multilinearization at all inputs, but I am not sure that it computes formally the multilinearization of the given polynomial (see my comments after Kaveh's answer). My construction (and yours) assumes that the multilinearization is computed formally. $\endgroup$ – Srikanth Nov 13 '10 at 2:43
12
$\begingroup$

In the case that the field $F$ is of size at least $2n$, I think this problem is hard. More specifically, I think that if the above can be efficiently solved for $F$ this large, then CNF-SAT has efficient randomized algorithms. Say we are given a CNF formula $\varphi$. One can easily come up with an arithmetic circuit $C$ that computes an ``arithmetization'' $p$ of $\varphi$, where the polynomial $p$ agrees with the formula $\varphi$ on $0$-$1$ inputs. Consider the multilinearization $q$ of $p$. Note that $q$ agrees with $p$ and hence $\varphi$ on $\{0,1\}^n$.

I claim that $q$ is non-zero iff $\varphi$ is satisfiable. Clearly, if $q=0$, then $\varphi$ cannot be satisfied. For the converse, one can show that any non-zero multilinear polynomial cannot vanish on all of $\{0,1\}^n$. This implies that a non-zero $q$ (and hence the corresponding $\varphi$) does not vanish at some input in $\{0,1\}^n$.

Therefore, checking for satisfiability of $\varphi$ is equivalent to checking if $q$ is non-zero. Say, now, that we could evaluate $q$ over a large field $F$. Then, using the Schwartz-Zippel Lemma, we could identity-test $q$ using an efficient randomized algorithm and check if it is the zero polynomial (the size of $F$ is used to upper bound the error in the Schwartz-Zippel Lemma).

$\endgroup$
  • $\begingroup$ It seems to me that F is a fixed field because there is nothing in the input that specifies F. Also note that the question assumes that field operations take unit time. $\endgroup$ – Kaveh Nov 11 '10 at 7:37
  • $\begingroup$ Thanks Srikanth. As Kaveh guessed I was indeed interested in the fixed finite field case, but this answer you gave helps me understand the question a bit better. $\endgroup$ – slimton Nov 11 '10 at 8:24
3
$\begingroup$

Assume that there is polytime algorithm that given $C(\vec{x}) \in F(\vec{x})$ and $\vec{a}$ computed the result of the multi-linearization of $C$ on $\vec{a}$. (w.l.o.g. I will assume that the output $\vec{b}$ will be a vector of $p$-bit binary numbers $b_i$ is $k$ iff the $b_{i,k}$ is one.)

Since $P \subseteq P/poly$, there is a polysize boolean circuit that given the encoding of the arithmetic circuit and the values for the variables computes the multi-linearization of the arithmetic circuit on the inputs. Let call this circuit $M$.

Let $C$ be an arbitrary arithmetic circuit. Fix the variables of the boolean circuit $M$ which describe the arithmetic circuit, so we have a boolean circuit computing the multi-linearization of $C$ on given inputs.

We can turn this circuit into an arithmetic circuit over $F_p$ by noting that $x^{p-1}$ is $1$ for all values but $0$ so first raise all inputs to the power $p-1$. Replace each $f \land g$ gate by multiplication $f.g$, each $f \lor g$ gate by $f+g-f.g$ and each $\lnot f$ gate by $1-f$.

By the assumption we made above about the format of the output, we can turn the output from binary to values over $F_p$. Take the output for $b_i$ and combine them to get $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$.

We can also convert the input given as values over $F_p$ to binary form since there are polynomials passing through any finite number of points. E.g. if we are working in $\bmod 3$, consider the polynomials $2x(x+1)$ and $2x(x+2)$ which give the first and the second bits of the input $x \in F_3$.

Combining these we have an arithmetic circuit over $F_p$ computing the multi-linearization of $C$ with size polynomail in the size of $C$.

$\endgroup$
  • 2
    $\begingroup$ It is not clear to me why the arithmetic circuit you have described computes the multilinearization of $C$, or indeed even a multilinear polynomial. I am only able to see that the arithmetic circuit computes some polynomial that agrees with the multilinearization of $C$ on $0$-$1$ inputs. $\endgroup$ – Srikanth Nov 12 '10 at 6:01
  • $\begingroup$ @Srikanth: the arithmetic version of the boolean circuit $M$ (with some inputs fixed) computes the multilinear version of $C$, it doesn't need to be a multilinear. Then the only problem is that input/output are in binary not values over $F_p$, so I just need to fix the encoding for input/output from binary to original input and output values. The resulting circuit is an arithmetic circuit that gets the values for variables of $C$, encodes them in binary, computes the value of the multilinearization of $C$ over those inputs and output the answer in binary, and then translate them back to $F_p$. $\endgroup$ – Kaveh Nov 12 '10 at 6:51
  • $\begingroup$ [continued] The result it is an arithmetic circuit with the same variables that $C$ has, and with the same outputs, and it is computing the multilinearization of $C$. $\endgroup$ – Kaveh Nov 12 '10 at 6:58
  • 2
    $\begingroup$ @Kaveh: Have you assumed that the input to the boolean circuit $M$ is of the same form as the output of $M$? In any case, I am still not convinced. It is perfectly possible for an arithmetic circuit to compute a polynomial $f$ that agrees with a polynomial $g$ at all inputs from the field and yet $f\neq g$. For example, the polynomial $x^p$ agrees with $x$ at all inputs, and yet they are not equal as polynomials. How do you know that the circuit $M$ is not simply computing a non-multilinear polynomial that agrees with the multilinearization of $C$ at all inputs? $\endgroup$ – Srikanth Nov 12 '10 at 7:15
  • $\begingroup$ @Srikanth: I have described the form of input and output in my answer. The input to $M$ is in binary, the output of $M$ is in the form stated above. I haven't said that it is multilinear, I have only said that it computes the multilinearization of the $C$. $\endgroup$ – Kaveh Nov 12 '10 at 9:47

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.