<p>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$.</p>

<p>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$.</p>

<p>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).</p>

CC BY-SA 2.5
2010-11-11T07:37:21.797Z
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.
Kaveh
CC BY-SA 2.5
2010-11-11T08:24:18.950Z
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.
slimton
CC BY-SA 2.5
2010-11-11T05:12:14.233Z
2010-11-11T05:22:51.503Z
2010-11-11T05:22:51.503Z
Srikanth
<p>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.)</p>

<p>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$.</p>

<p>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.</p>

<p>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$. </p>

<p>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}}$.</p>

<p>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$.</p>

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

CC BY-SA 2.5
2010-11-14T22:22:21.203Z
@Kaveh: I think I understand your construction except for the encoding scheme of the output. Why do the $b_{i,k}$'s have two indices? The output is a single element of the field. So, let's say the output of the boolean circuit is a bit-vector $b_k$, indexed by the elements of the field, that has exactly one $1$. Then you recover the output by taking the sum $\sum_{k} k b_k$. Now: why do you say that this construction contradicts the hypothesis that the permanent does not have polynomial-size circuits over $F_p$ (for $p \not= 2$)? How do you get the polynomial-size circuit for the permanent?
slimton
CC BY-SA 2.5
2010-11-15T02:10:08.340Z
@slimton: I assumed that we have more than one gate, if you are only interested in single output you can ignore the first index. About permanent, there was a confusion, I asked if my construction contradicts something in arithmetic complexity and Srikanth answered positively assuming more than what my  construction gave. Currently I don't know how to get a polysize circuit for permanent. So I remove the quote from Sriknath's comment.
Kaveh
CC BY-SA 2.5
2010-11-21T11:55:59.453Z
@Kaveh: Ok, I got it now. So my question remains unanswered... Thanks anyway.
slimton
CC BY-SA 2.5
2010-11-22T01:49:51.190Z
@slimton: Yes, it is still unanswered. Sorry that couldn't help much.
Kaveh
CC BY-SA 2.5
2010-11-12T06:01:01.340Z
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.
Srikanth
CC BY-SA 2.5
2010-11-12T06:51:48.820Z
@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$.
Kaveh
CC BY-SA 2.5
2010-11-12T06:58:55.630Z
[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$.
Kaveh
CC BY-SA 2.5
2010-11-12T07:15:03.633Z
@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?
Srikanth
CC BY-SA 2.5
2010-11-12T09:47:01.010Z
@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$*.
Kaveh
CC BY-SA 2.5
2010-11-12T04:28:09.583Z
2010-11-15T02:10:50.960Z
2010-11-15T02:10:50.960Z
Kaveh
<p>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.</p>

<p>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)$.</p>

<p>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$).</p>

CC BY-SA 2.5
2010-11-10T22:00:27.663Z
Next time, please be careful not to make new tags unintentionally, because the system does not give any warning when you enter new tags (as long as you have rep points 200).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-11T07:40:44.500Z
1. What is the model of computation? Is it arithmetic circuits  (and polynomial time means polynomial size and depth)? 2. if we are not talking about very small complexity classes and polytime is not one of them, then the problem seems to be equivalent to computing the output of a given closed circuit (a circuit with no input variables). Then it seems to me that the usual algorithm for evaluating a closed circuit should solve it. Could you please explain what are the obstacles you are facing that don't allow you to solve the problem using the trivial algorithm?
Kaveh
CC BY-SA 2.5
2010-11-11T08:34:20.763Z
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.
slimton
CC BY-SA 2.5
2010-11-11T10:53:38.737Z
@slimton: You don't need to replace them that way, you only need to substitute the input node for each variable with a node for the value. Here I was assuming that we can use any element from the field in our circuit in the same way that we can use the values 0 and 1. Let me clarify what I have asked above: why can't we use an algorithm similar to the polytime algorithm for computing circuit value problem? (note that you don't need to go over all paths one by one). (btw, could you clarify what is the model of computation we are using in this problem?) please use a @kaveh so I get notified.
Kaveh
CC BY-SA 2.5
2010-11-11T12:01:21.760Z
@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.
slimton
CC BY-SA 2.5
2010-11-11T15:56:44.187Z
I now see the problem! btw, just a simple observation which might or might not help, it seems to me that if there was a polytime algorithm for this problem, that would imply that there is an arithmetic circuit with polynomial size increase w.r.t. the given arithmetic circuit computing the multilinearazation of the arithmetic circuit. Doesn't this contradict some result in arithmetic circuit complexity?
Kaveh
CC BY-SA 2.5
2010-11-12T02:05:48.093Z
@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$.
Srikanth
CC BY-SA 2.5
2010-11-12T06:01:40.127Z
@Sriknth, I posted it below.
Kaveh
CC BY-SA 2.5
2010-11-13T00:58:12.117Z
@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.
Joshua Grochow
CC BY-SA 2.5
2010-11-13T02:43:14.833Z
@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.
Srikanth
CC BY-SA 2.5
2010-11-13T04:32:06.900Z
@Sriknath: I think there was a misunderstanding when I wrote that the circuit computes the multilinearization of $C$, I think you interpreted it as something more than what I meant. I need to think a little more about this.
Kaveh
CC BY-SA 2.5
2010-11-13T04:38:59.393Z
@Kaveh: Sure. I think I was also not clear about the assumptions I was making.
Srikanth
<cc.complexity-theory><polynomials>
Evaluating the multilinearization of an arithmetic circuit?
slimton
# Evaluating the multilinearization of an arithmetic circuit?

(Asked by: username_0 on 2010-11-10)

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$).

**Tags:** cc.complexity-theory, polynomials
> **Comments:**
> **username_1**: Next time, please be careful not to make new tags unintentionally, because the system does not give any warning when you enter new tags (as long as you have rep points 200).  
> **username_2**: 1. What is the model of computation? Is it arithmetic circuits  (and polynomial time means polynomial size and depth)? 2. if we are not talking about very small complexity classes and polytime is not one of them, then the problem seems to be equivalent to computing the output of a given closed circuit (a circuit with no input variables). Then it seems to me that the usual algorithm for evaluating a closed circuit should solve it. Could you please explain what are the obstacles you are facing that don't allow you to solve the problem using the trivial algorithm?  
> **username_0**: 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.  
> **username_2**: @slimton: You don't need to replace them that way, you only need to substitute the input node for each variable with a node for the value. Here I was assuming that we can use any element from the field in our circuit in the same way that we can use the values 0 and 1. Let me clarify what I have asked above: why can't we use an algorithm similar to the polytime algorithm for computing circuit value problem? (note that you don't need to go over all paths one by one). (btw, could you clarify what is the model of computation we are using in this problem?) please use a @kaveh so I get notified.  
> **username_0**: @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.  
> **username_2**: I now see the problem! btw, just a simple observation which might or might not help, it seems to me that if there was a polytime algorithm for this problem, that would imply that there is an arithmetic circuit with polynomial size increase w.r.t. the given arithmetic circuit computing the multilinearazation of the arithmetic circuit. Doesn't this contradict some result in arithmetic circuit complexity?  
> **username_3**: @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$.  
> **username_2**: @Sriknth, I posted it below.  
> **username_4**: @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.  
> **username_3**: @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.  
> **username_2**: @Sriknath: I think there was a misunderstanding when I wrote that the circuit computes the multilinearization of $C$, I think you interpreted it as something more than what I meant. I need to think a little more about this.  
> **username_3**: @Kaveh: Sure. I think I was also not clear about the assumptions I was making.  

---

## 2 answers

### Answer by username_3 on 2010-11-11. Score: 12

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).

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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.  

---

### Answer by username_2 on 2010-11-12. Score: 3

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$.

> **Comments:**
> **username_3**: 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.  
> **username_2**: @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$.  
> **username_2**: [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$.  
> **username_3**: @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?  
> **username_2**: @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$*.  
> **username_0**: @Kaveh: I think I understand your construction except for the encoding scheme of the output. Why do the $b_{i,k}$'s have two indices? The output is a single element of the field. So, let's say the output of the boolean circuit is a bit-vector $b_k$, indexed by the elements of the field, that has exactly one $1$. Then you recover the output by taking the sum $\sum_{k} k b_k$. Now: why do you say that this construction contradicts the hypothesis that the permanent does not have polynomial-size circuits over $F_p$ (for $p \not= 2$)? How do you get the polynomial-size circuit for the permanent?  
> **username_2**: @slimton: I assumed that we have more than one gate, if you are only interested in single output you can ignore the first index. About permanent, there was a confusion, I asked if my construction contradicts something in arithmetic complexity and Srikanth answered positively assuming more than what my  construction gave. Currently I don't know how to get a polysize circuit for permanent. So I remove the quote from Sriknath's comment.  
> **username_0**: @Kaveh: Ok, I got it now. So my question remains unanswered... Thanks anyway.  
> **username_2**: @slimton: Yes, it is still unanswered. Sorry that couldn't help much.  

---

