# Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root, and "satisfiable" if it is 1. (I use interpolating in a very loose sense here). It seems plausible that the degree/number of turning points of the resulting polynomial corresponds loosely to how "complex" the formula is.

To give a trivial example,

$a \oplus b$ is quardratic, $(1-ab)(1-(1-a)(1-b))$

while

$a \wedge b$ is $ab$, linear.

I believe an argument of this sort was used by Smolensky to show that PARITY is not in $AC^0$. I wonder, however, if there is there a more precise interpretation of

• The Degree of the Polynomial
• The Number of Turning Points in the Polynomial?

Thanks!

• What's a "turning point"? Do you mean critical point (a point where all partial derivatives are zero)? – Jeffε Dec 8 '10 at 22:15
• @JeffE sorry about the lack of clarity. I actually mean a point where any of the partial derivatives are zero, and it is not a saddle point. I think this is intuitively the amount the polynomial "folds" – gabgoh Dec 9 '10 at 1:53
• Ah. But there isn't a number of fold points. For a generic function on $n$ variables, the set of points where (say) the first partial derivative is zero is a collection of disjoint $(n-1)$-dimensional manifolds in $\mathbb{R}^n$, not a finite set of points. – Jeffε Dec 9 '10 at 3:09
• @JeffE Good point. I think the second part of my problem isn't well posed. Intuitively, there seems to be a way to characterize how much a polynomial "twists", but I'm not sure what that is. I'll have to think about it more. I have edited it out of my question. – gabgoh Dec 9 '10 at 6:24
• Maybe you meant the number of local extrema? – Tsuyoshi Ito Dec 12 '10 at 20:35