<p>Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could also consider a depth-2 circuits with a multiplication gate at the top). </p>

<p>Degree is very closely related to the <em>depth</em> of algebraic circuits, as in the results of Hyafil and Valiant-Skyum-Berkowitz-Rackoff.</p>

CC BY-SA 3.0
2014-07-20T17:32:34.027Z
2014-07-20T17:32:34.027Z
Joshua Grochow
<p>Expressing a boolean function <span class="math-container">$f$</span> <span class="math-container">$:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$</span> using a polynomial <span class="math-container">$P(x_{1},...,x_{n})$</span>, where <span class="math-container">$x_{1},...,x_{n}$</span> may be integer, finite fields, or other fields.</p>
<p>One of the most popular examples is Fourier Analysis e.g.  <a href="http://analysisofbooleanfunctions.org/" rel="nofollow noreferrer">http://analysisofbooleanfunctions.org/</a> .</p>
<p>Another topic is transforming small depth circuits to polynomials over the integers with small degree and  magnitudes of small weights. For example, the transformation from ACC circuits to polynomials proved by Yao and Beigel and Tarui is notable.</p>
<p>My questions are:</p>
<blockquote>
<p>Qestion A. Is there a list of results about lower bounds and remarkable techniques for polynomials computing boolean functions.
I know Williams' separation between NEXP and ACC.</p>
<p>Question B. Does the recent separation result about ACC <span class="math-container">$\circ $</span> THR circuits by Williams contain some interpretation relating with polynomials computing boolean funcitons ?</p>
<p>Question C. Is proving lower bounds on the number of monomials or the degree or other  formally defined complexity measures related with algebraic complexity theory and arithmetic circuit complexity established by Valiant with VP v. VNP problem??</p>
<p>I am reading the survey written by Shiplka, and have met a difference between boolean complexity and arithmetic complexity: semantic versus syntatic.</p>
</blockquote>
<p>Here is a response to the J's question.</p>
<p>The survey has a remark about the difference between polynomial and polynomial function.</p>
<p>Taking an example, <span class="math-container">$x^{2}-x$</span> is a polynomial which is NOT identicdally zero but is a polynomial function <span class="math-container">$GF(2)^{n}\rightarrow GF(2)$</span> identically zero over <span class="math-container">$GF(2)$</span>.</p>
<p>In algebraic complexity, Valiant's question is  about complexity of the expressing polynomial (not polynomial function).</p>
<p>However, I mainly want to consider polynomial functions. Thanks.</p>

CC BY-SA 3.0
2014-07-20T17:32:19.373Z
What do you mean that "semantic vs syntactic" is a difference between boolean and algebraic complexity? Also, FYI, most people use "algebraic circuit" and "arithmetic circuit" as synonyms. (Given the relationship between circuit complexity and algebraic geometry, I'm trying to get people to use them more the way algebraic geometers / number theorists do, where "algebraic" typically means over an [algebraically closed] field, and "arithmetic" typically means over $\mathbb{Z}$, $\mathbb{Q}$, or number fields, but only with limited success.)
Joshua Grochow
<cc.complexity-theory><circuit-complexity><boolean-functions><algebraic-complexity><arithmetic-circuits>
Lower bounds for Polynomials computing the boolean functions
shen
# Lower bounds for Polynomials computing the boolean functions

(Asked by: username_0 on 2014-07-20)

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x\_{1},...,x\_{n})$, where $x\_{1},...,x\_{n}$ may be integer, finite fields, or other fields.

One of the most popular examples is Fourier Analysis e.g. <http://analysisofbooleanfunctions.org/> .

Another topic is transforming small depth circuits to polynomials over the integers with small degree and magnitudes of small weights. For example, the transformation from ACC circuits to polynomials proved by Yao and Beigel and Tarui is notable.

My questions are:

> Qestion A. Is there a list of results about lower bounds and remarkable techniques for polynomials computing boolean functions.
> I know Williams' separation between NEXP and ACC.
>
> Question B. Does the recent separation result about ACC $\circ $ THR circuits by Williams contain some interpretation relating with polynomials computing boolean funcitons ?
>
> Question C. Is proving lower bounds on the number of monomials or the degree or other formally defined complexity measures related with algebraic complexity theory and arithmetic circuit complexity established by Valiant with VP v. VNP problem??
>
> I am reading the survey written by Shiplka, and have met a difference between boolean complexity and arithmetic complexity: semantic versus syntatic.

Here is a response to the J's question.

The survey has a remark about the difference between polynomial and polynomial function.

Taking an example, $x^{2}-x$ is a polynomial which is NOT identicdally zero but is a polynomial function $GF(2)^{n}\rightarrow GF(2)$ identically zero over $GF(2)$.

In algebraic complexity, Valiant's question is about complexity of the expressing polynomial (not polynomial function).

However, I mainly want to consider polynomial functions. Thanks.

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, algebraic-complexity, arithmetic-circuits

> **Comments:**
> **username_1**: What do you mean that "semantic vs syntactic" is a difference between boolean and algebraic complexity? Also, FYI, most people use "algebraic circuit" and "arithmetic circuit" as synonyms. (Given the relationship between circuit complexity and algebraic geometry, I'm trying to get people to use them more the way algebraic geometers / number theorists do, where "algebraic" typically means over an [algebraically closed] field, and "arithmetic" typically means over $\mathbb{Z}$, $\mathbb{Q}$, or number fields, but only with limited success.)  

---

## 1 answers

### Answer by username_1 on 2014-07-20. Score: 2

Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could also consider a depth-2 circuits with a multiplication gate at the top).

Degree is very closely related to the *depth* of algebraic circuits, as in the results of Hyafil and Valiant-Skyum-Berkowitz-Rackoff.


---

