To refer to this page use:
|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.  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.|
|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|
|Pages:||232 - 243|
|Type of Material:||Conference Article|
|Series/Report no.:||Lecture Notes in Computer Science;|
|Journal/Proceeding Title:||Automata, Languages, and Programming|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.