TY - GEN

T1 - Direct product via round-preserving compression

AU - Braverman, Mark

AU - Rao, Anup

AU - Weinstein, Omri

AU - Yehudayoff, Amir

PY - 2013/7/23

Y1 - 2013/7/23

N2 - 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 sucr(μ n, fn, T) ≤ exp(-Ω(n/r2)). Here we prove that if suc7r(μ, f, C) ≤ 2/3 and T ≪ (C - Ω(r log r))·n then sucr(μn, fn, T) ≤ exp(-Ω(n)). Up to a log r factor, our result asymptotically matches the upper bound on suc7r (μn ,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.

AB - 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 sucr(μ n, fn, T) ≤ exp(-Ω(n/r2)). Here we prove that if suc7r(μ, f, C) ≤ 2/3 and T ≪ (C - Ω(r log r))·n then sucr(μn, fn, T) ≤ exp(-Ω(n)). Up to a log r factor, our result asymptotically matches the upper bound on suc7r (μn ,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.

UR - http://www.scopus.com/inward/record.url?scp=84880297866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880297866&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_20

DO - 10.1007/978-3-642-39206-1_20

M3 - Conference contribution

AN - SCOPUS:84880297866

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 232

EP - 243

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -