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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The unbounded-error communication complexity of a Boolean function F is the limit of the ε-error randomized complexity of F as ε → 1/2. Communication complexity with weakly unbounded error is defined similarly but with an additive penalty term that depends on 1/2−ε . Explicit functions are known whose two-party communication complexity with unbounded error is logarithmic compared to their complexity with weakly unbounded error. Chattopadhyay and Mande (ECCC Report TR16-095, Theory of Computing 2018) recently generalized this exponential separation to the number-on-the-forehead multiparty model. We show how to derive such an exponential separation from known two-party work, achieving a quantitative improvement along the way. We present several proofs here, some as short as half a page. In more detail, we construct a k-party communication problem F : ({0,1}n)k→{0,1} that has complexity O(logn) with unbounded error and Ω( √ n/4k) with weakly unbounded error, reproducing the bounds of Chattopadhyay and Mande. In addition, we prove a quadratically stronger separation of O(logn) versus Ω(n/4k) using a nonconstructive argument. ACM Classification: F.1.3, F.2.3 AMS Classification: 68Q17, 68Q15

On multiparty communication with large versus unbounded error