Processing math: 100%
\ie\cf
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
  \newcommand{\R} % real numbers
  \newcommand{\N}} % natural numbers
  \newcommand{\Z} % integers
  \newcommand{\F} % a field
  \newcommand{\Q} % the rationals
  \newcommand{\C}{\mathbb{C}} % the complexes
  \newcommand{\poly}}
  \newcommand{\polylog}}
  \newcommand{\loglog}}}
  \newcommand{\zo}{\{0,1\}}
  \newcommand{\suchthat}
  \newcommand{\pr}[1]{\Pr\left[#1\right]}
  \newcommand{\deffont}{\em}
  \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}
  \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation
  \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance
  \newcommand{\xor}{\oplus}
  \newcommand{\GF}{\mathrm{GF}}
  \newcommand{\eps}{\varepsilon}
  \notag
\no
Back to Arithmetic Circuits
Back to notes

Useful tricks

20%

Identities

Newton identity

Newton identity provides a bridge between Symk and Powk. For our interest in arithmetic circuits, Newton identity tells us that Symd has a ΣΠΣΛ circuit of size 2O(√d)⋅poly(n). Note that the resulting circuit is homogeneous. Recall that there is nΩ(d) lower bound for ΣΛΣ circuits computing Symd.

For any k∈[n], we have Symk=1k!|Pow110⋯0Pow2Pow12⋯0⋮⋮⋱⋯0Powk−1Powk−2⋯Pow1k−1PowkPowk−1⋯Pow2Pow1|. Specifically, one can write x1x2⋯xk=∑a: ∑iiai=kαa(Pow1)a1(Pow2)a2⋯(Powk)ak.

Applications:

Ryser-Fischer identity

Ryser-Fischer identity expresses multilinear monomial into sums of the power of sum. To our interest in arithmetic circuits, it implies that one can replace monomial x1x2⋯cd with a size 2d ΣΛΣ circuit. Note that the circuit is homogeneous.

For any d∈N, we have x1x2⋯xd=∑S⊆[d](−1)d−|S|(∑i∈Sxi)d.

The proof is based on simple inclusion-exclusion principle so here we omit the details.

Duality trick

The duality trick converts ΛΣΛ circuit to ΣΠΣ circuit.