1
$\begingroup$

Here is a question from Computational Complexity by Arora and Barak:

Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (This is Exercise 6 in the chapter on circuit lower bounds.)

How do I approach this problem?

$\endgroup$
8
  • $\begingroup$ What have you tried? Have you tried the case $n=2$? $n=3$? We discourage questions that are just the statement of an exercise-style task and a request for us to solve it. $\endgroup$
    – D.W.
    Oct 10 '20 at 19:29
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/3859524/14578, cs.stackexchange.com/q/131041/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Oct 10 '20 at 19:30
  • $\begingroup$ Yes, my approach actually is convert the domain for $\{0,1\}^n->\{-1,1\}^n$ by taking $y=1-2x, x \in \{0,1\}^n$. Thus all the polynomials can be represented as multinomials. But the arithmetization of OR gives us a n degree multinomial directly, and we are asking whether there is another multinomial of less degree computing OR. This is where I am stuck. Also the transformation we are doing here does not change the degree. $\endgroup$ Oct 10 '20 at 19:40
  • $\begingroup$ You've restated the problem. I suggest that you try to prove it for $n=2$ first, and see how much progress you can make. $\endgroup$
    – D.W.
    Oct 10 '20 at 20:05
  • $\begingroup$ Here is what I have thought. I tried to approach for AND. For n=2, lets suppose we have a degree 1 polynomial computing AND. If we take the monomials containing $x_1$, and take $x_1=0$, we get the result zero. So, the other monomials in which $x_1$ is not present will be zero automatically. Similar with $x_1$, so we can conclude $x_1,x_2$ are present in the same monomial. But that makes its degree 2. Now, if we consider OR circuit of degree 1 and convert to AND by negating the variables, we get a contradiction as negating variable wont change degree. But this is not very formal only intuitive $\endgroup$ Oct 11 '20 at 5:46
1
$\begingroup$

Let $AND:\{0,1\}^n\mapsto\{0,1\}$ be a polynomial in $GF(q), q\geq 2$. Notice that the polynomial can't have a constant term (the constant term is zero), because $AND(0,...,0) = 0$. Meaning we can write the polynomial as: $$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$ We now claim that every non-zero summand in $AND$ contains $x_i$. Suppose that there are a set of summands not containing $x_i$. Choose the smallest (by amount of different parameters contained) of them. Notice that this term is uniquely identified by a set $U \subset [1,n]\backslash\{i\}$. Now set $x_u = 1, u\in U$ and $x_v = 0, v\notin U$ and that there is no proper subsets of $U$ whose associated term is non-zero, because $|U|$ was chosen to be minimal. $$AND(x_1,...,x_n) = a_U$$ This implies $a_U = 0$, because $i\notin U \land x_i = 0$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $x_i$. This applies to all $i\in[1,n]$, hence the degree of $AND$ is $n$.

We can denote $OR$ as $OR(x_1,...,x_n) = 1-AND(1-x_1,...,1-x_n)$ and likewise $AND(x_1,...,x_n) = 1-OR(1-x_1,...,1-x_n)$ by De Morgan's Law. Thus $AND$ and $OR$ must have the same degree.

$\endgroup$
1
$\begingroup$

Let $f\colon \{0,1\}^n \to \mathit{GF}(q)$. Then $$ f(x) = \sum_{y \in \{0,1\}^n} f(y) \prod_{i\colon y_i=0} (1-x_i) \prod_{i\colon y_i=1} x_i. $$ This shows that any function from $\{0,1\}^n$ to $\mathit{GF}(q)$ can be represented as a multilinear polynomial.

Now let us show that the representation is unique. This follows from dimension considerations (the space of all such functions has dimension $2^n$, which coincides with the dimension of the space of multilinear polynomials), but we can also prove it directly. If some function has two different representations $P,Q$, then $P-Q$ is a non-zero multilinear polynomial that vanishes on $\{0,1\}^n$. Let $m$ be a monomial in $P-Q$ of minimal degree, appearing with coefficient $c \neq 0$, and let $y \in \{0,1\}^n$ be the point defined as follows: $y_i = 1$ if $x_i$ appears in $m$, and $y_i = 0$ otherwise. Then $(P-Q)(y) = cm(y) = c \neq 0$, contradiction.

Suppose that $P$ is a polynomial representing the OR function. If $P$ is not multilinear, we can replace every occurrence of $x_i^d$ for $d \geq 1$ with $x_i$, obtaining another representation $Q$ of OR whose degree is at most the degree of $P$. According to the above, this representation is unique, and so it must be the following: $$ Q(x) = 1-\prod_{i=1}^n (1-x_i). $$ Thus $\deg(P) \geq \deg(Q) = n$.

$\endgroup$

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.