How Hard is Computing Parity with Noisy Communications?

Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath +1

We show a tight lower bound of $\Omega (N\log \log N)$ on the number of transmissions required to compute the parity of $N$ input bits with constant error in a noisy communication networ…