### 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 log^{3/2}T ⋘ (C - 1) √ n and suc(μ, f,C) < 2 3 , then suc(μn, f^{n}, 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)).

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |

Pages | 746-755 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2013 |

Event | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States Duration: Oct 27 2013 → Oct 29 2013 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |
---|---|

Country | United States |

City | Berkeley, CA |

Period | 10/27/13 → 10/29/13 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Fingerprint Dive into the research topics of 'Direct products in communication complexity'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013*(pp. 746-755). [6686211] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.85