Direct product via round-preserving compression

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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

19 Scopus citations


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
Number of pages12
EditionPART 1
StatePublished - 2013
Externally publishedYes
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


Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this