1
$\begingroup$

I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the symmetrization technique?

For instance, it is used in Lemma $5$ in this paper http://www.csee.usf.edu/~tripathi/Publication/polynomial-degree-conference.pdf

$\endgroup$
3
$\begingroup$

Over $0/1$ inputs we have $$ \begin{align*} (y_1+\cdots+y_N)^0 &= 1 \\ (y_1+\cdots+y_N)^1 &= \sum_i y_i \\ (y_1+\cdots+y_N)^2 &= \sum_i y_i+2\sum_{i<j} y_iy_j \\ (y_1+\cdots+y_N)^3 &= \sum_i y_i+6\sum_{i<j} y_iy_j + 6\sum_{i<j<k} y_iy_jy_k \end{align*} $$ And so on. It follows that for $0/1$ inputs, $p_{sym}$ can be written as a linear combination of $(y_1+\cdots+y_n)^0,\ldots,(y_1+\cdots+y_n)^d$, where $d$ is its degree. This linear combination can also be viewed as a polynomial $\tilde{p}$ in $y_1+\cdots+y_n$, which is equal to $p_{sym}$ for $0/1$ inputs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So do we have other tricks when the group is not the full symmetric group? $\endgroup$ – 1.. Nov 30 '14 at 19:07
  • 1
    $\begingroup$ Perhaps. But the point of symmetrization is that you can symmetrize the function. $\endgroup$ – Yuval Filmus Dec 1 '14 at 0:06
  • $\begingroup$ If you look at invariant theory, perhaps what I am asking cannot be done since $S_n$ and the cyclic groups $C_2$ are special (Chevalley theorem). $\endgroup$ – 1.. Dec 1 '14 at 1:37
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – 1.. Dec 1 '14 at 1:38

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.