Skip to main content

Direct Product via Round-Preserving Compression

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

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. [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

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.