Skip to main content

Direct products in communication complexity

Author(s): Braverman, Mark; Weinstein, O; Rao, A; Yehudayoff, A

To refer to this page use:
Abstract: We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f,C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μn be the product distribution on n inputs and fn denote the function that computes n copies of f on these inputs. We prove that if T log3/2T ⋘ (C - 1) √ n and suc(μ, f,C) < 2 3 , then suc(μn, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: As long as T log 2 T ⋘ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)). Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 26-Oct-2013
Electronic Publication Date: 19-Oct-2013
Citation: Braverman, M, Weinstein, O, Rao, A, Yehudayoff, A. (2013). Direct products in communication complexity. 746 - 755. doi:10.1109/FOCS.2013.85
DOI: doi:10.1109/FOCS.2013.85
Pages: 746 - 755
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.