We obtain a strong direct product theorem for two-party bounded round communication complexity. Let suc_r(μ,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. have recently showed that if suc_r(μ, f, C) ≤ 2/3 and T (C - Ω(r~2)) • n/r, then suc_r(μ~n, f~n,T) ≤ exp(-Ω(n/r~2)). Here we prove that if suc_(7r)(μ, f, C) ≤ 2/3 and T (C - Ω(rlog r)) • n then suc_r(μ~n, f~n,T) ≤ exp(-Ω(n)). Up to a log r factor, our result asymptotically matches the upper bound on suc_(7r)(μ~n,f~n,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.
展开▼
