6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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.) $\endgroup$
    – Joshua Grochow
    Jul 20, 2014 at 17:32

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.