Direct product via round-preserving compression

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

We obtain a strong direct product theorem for two-party bounded round communication complexity. Let sucr (μ, f, C) denote the maximum success probability of an r-round communication protocol that uses at most C bits of communication in computing f(x,y) when (x,y) ∼ μ. Jain et al. [12] have recently showed that if sucr(μ, f, C) ≤ 2/3 and T ≪, (C - Ω(r2))·n/r, then sucrn, fn, T) ≤ exp(-Ω(n/r2)). Here we prove that if suc7r(μ, f, C) ≤ 2/3 and T ≪ (C - Ω(r log r))·n then sucrn, fn, T) ≤ exp(-Ω(n)). Up to a log r factor, our result asymptotically matches the upper bound on suc7rn ,fn, T) given by the trivial solution which applies the per-copy optimal protocol independently to each coordinate. The proof relies on a compression scheme that improves the tradeoff between the number of rounds and the communication complexity over known compression schemes.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages232-243
Number of pages12
EditionPART 1
DOIs
StatePublished - Jul 23 2013
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
CountryLatvia
CityRiga
Period7/8/137/12/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Direct product via round-preserving compression'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Rao, A., Weinstein, O., & Yehudayoff, A. (2013). Direct product via round-preserving compression. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings (PART 1 ed., pp. 232-243). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-39206-1_20