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

Representations of Boolean functions by real polynomials play an importantrole in complexity theory. Typically, one is interested in the least degree ofa polynomial p(x_1,...,x_n) that approximates or sign-represents a givenBoolean function f(x_1,...,x_n). This article surveys a new and growing body ofwork in communication complexity that centers around the dual objects, i.e.,polynomials that certify the difficulty of approximating or sign-representing agiven function. We provide a unified guide to the following results, completewith all the key proofs:  (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds onthe threshold degree of a Boolean function into upper bounds on the discrepancyof a related function;  (2) Two different methods for proving lower bounds on bounded-errorcommunication based on the approximate degree: Sherstov's pattern matrix methodand Shi and Zhu's block composition method;  (3) Extension of the pattern matrix method to the multiparty model, obtainedby Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improvedlower bounds for DISJOINTNESS;  (4) David and Pitassi's separation of NP and BPP in multiparty communicationcomplexity for k=(1-eps)log n players.

Communication Lower Bounds Using Dual Polynomials