= Algebraic normal form
{title2=$f(z)=\bigoplus_{S\subseteq[d]}c_S\prod_{i\in S}z_i$}
{wiki}
The algebraic normal form is the unique multilinear polynomial representation of a <Boolean function> over the field with two elements, using <exclusive or> for addition and ordinary bit multiplication for products. The empty product is one. Existence and uniqueness follow by induction from $f(z',z_d)=f(z',0)\oplus z_d(f(z',0)\oplus f(z',1))$: the first polynomial supplies all coefficients not containing $z_d$, and the difference supplies exactly those that do. For split inputs $(x,y)$, each monomial factors into one locally computed product of Alice's bits and one of Bob's bits, yielding a <separated Boolean decomposition>.
Back to article page
