= Separated Boolean decomposition
{title2=$f(x,y)=\bigoplus_{\xi\in\{0,1\}^m}\mathbf1_{\{x=\xi\}}f(\xi,y)$}
Every <Boolean function> of distributed inputs is an <exclusive or> of products of locally computable bits. The displayed identity follows because exactly one indicator is one. It uses at most $2^m$ terms, each a function of $x$ times a function of $y$; exchanging the two input roles gives at most $2^n$ terms. This elementary truth-table factorization is useful for distributed computation with <PR boxes> and does not depend on a probabilistic approximation.
Back to article page
