Article ID Journal Published Year Pages File Type
437638 Theoretical Computer Science 2010 5 Pages PDF
Abstract

For n=2kn=2k, we know that the size of a smallest AND/OR/NOT formula computing the Boolean function Parity(x1,…,xn)=Odd(x1,…,xn) is exactly n2n2: For any nn, it is at least n2n2 by the classical Khrapchenko bound, and for n=2kn=2k we easily obtain a formula of size n2n2 by writing and recursively expanding Odd(x1,…,xn)=[Odd(x1,…,xn/2)∧Even(xn/2+1,…,xn)]∨[Even(x1,…,xn/2)∧Odd(xn/2+1,…,xn)]. We show that for n=2kn=2k the formula obtained above is an essentially unique one that computes Parity(x1,…,xn) with size n2n2. In the equivalent framework of the Karchmer–Wigderson communication game, our result means that an optimal protocol for the parity of 2k2k variables is essentially unique.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,