# Direct Product via Round-Preserving Compression

## Author(s): Braverman, Mark; Rao, Anup; Weinstein, Omri; Yehudayoff, Amir

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1fv65
 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. Publication Date: 2013 Citation: Braverman, Mark, Anup Rao, Omri Weinstein, and Amir Yehudayoff. "Direct Product via Round-Preserving Compression." Automata, Languages, and Programming (2013): 232-243. doi:10.1007/978-3-642-39206-1_20 DOI: 10.1007/978-3-642-39206-1_20 ISSN: 0302-9743 Pages: 232 - 243 Type of Material: Conference Article Series/Report no.: Lecture Notes in Computer Science; Journal/Proceeding Title: Automata, Languages, and Programming Version: Author's manuscript