English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show a tight lower bound of $\Omega(N \log\log N)$ on the number oftransmissions required to compute the parity of $N$ input bits with constanterror in a noisy communication network of $N$ randomly placed sensors, eachhaving one input bit and communicating with others using local transmissionswith power near the connectivity threshold. This result settles the lower boundquestion left open by Ying, Srikant and Dullerud (WiOpt 06), who showed how thesum of all the $N$ bits can be computed using $O(N \log\log N)$ transmissions.The same lower bound has been shown to hold for a host of other functionsincluding majority by Dutta and Radhakrishnan (FOCS 2008).  Most works on lower bounds for communication networks considered mostly thefull broadcast model without using the fact that the communication in realnetworks is local, determined by the power of the transmitters. In fact, infull broadcast networks computing parity needs $\theta(N)$ transmissions. Toobtain our lower bound we employ techniques developed by Goyal, Kindler andSaks (FOCS 05), who showed lower bounds in the full broadcast model by reducingthe problem to a model of noisy decision trees. However, in order to capturethe limited range of transmissions in real sensor networks, we adapt theirdefinition of noisy decision trees and allow each node of the tree access toonly a limited part of the input. Our lower bound is obtained by exploitingspecial properties of parity computations in such noisy decision trees.

How Hard is Computing Parity with Noisy Communications?