Direct Product via Round-Preserving Compression

Abstract

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. [12] have recently showed that if 𝗌𝗎𝖼𝑟(𝜇,𝑓,𝐶)≤23 and 𝑇≪(𝐶−Ω(𝑟2))⋅𝑛𝑟 , then 𝗌𝗎𝖼𝑟(𝜇𝑛,𝑓𝑛,𝑇)≤exp(−Ω(𝑛/𝑟2)) . Here we prove that if 𝗌𝗎𝖼7𝑟(𝜇,𝑓,𝐶)≤23 and T ≪ (C − Ω(r logr)) ·n then 𝗌𝗎𝖼𝑟(𝜇𝑛,𝑓𝑛,𝑇)≤exp(−Ω(𝑛)) . Up to a logr 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.