Communication Lower Bounds Using Dual Polynomials Export

@misc{citeulike:2801039, abstract = {Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x\_1,...,x\_n) that approximates or sign-represents a given Boolean function f(x\_1,...,x\_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players.}, archivePrefix = {arXiv}, author = {Sherstov, Alexander A.}, citeulike-article-id = {2801039}, citeulike-linkout-0 = {http://arxiv.org/abs/0805.2135}, citeulike-linkout-1 = {http://arxiv.org/pdf/0805.2135}, eprint = {0805.2135}, keywords = {complexity, printed}, month = {May}, posted-at = {2008-05-15 09:44:19}, priority = {2}, title = {Communication Lower Bounds Using Dual Polynomials}, url = {http://arxiv.org/abs/0805.2135}, year = {2008} }

TY - ELEC ID - citeulike:2801039 L3 - citeulike-article-id:2801039 N2 - Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers around the dual objects, i.e., polynomials that certify the difficulty of approximating or sign-representing a given function. We provide a unified guide to the following results, complete with all the key proofs: (1) Sherstov's Degree/Discrepancy Theorem, which translates lower bounds on the threshold degree of a Boolean function into upper bounds on the discrepancy of a related function; (2) Two different methods for proving lower bounds on bounded-error communication based on the approximate degree: Sherstov's pattern matrix method and Shi and Zhu's block composition method; (3) Extension of the pattern matrix method to the multiparty model, obtained by Lee and Shraibman and by Chattopadhyay and Ada, and the resulting improved lower bounds for DISJOINTNESS; (4) David and Pitassi's separation of NP and BPP in multiparty communication complexity for k=(1-eps)log n players. TI - Communication Lower Bounds Using Dual Polynomials KW - complexity KW - printed AU - Sherstov, Alexander PY - 2008/May/14/ UR - http://arxiv.org/abs/0805.2135 ER -