Direct product via round-preserving compression.
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff · 2013
Abstract. 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) ≤ 23 and T (C − Ω(r2)) · n r, then sucr(µ