2020/08/17 by Rahul Jain, Jain, Rahul
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2008.07188
We show a near optimal direct-sum theorem for the two-party randomized communication complexity. Let f⊆ X × Y× Z be a relation, ε> 0 and k be an integer. We show, Rpubε(fk) ⋅ log(Rpubε(fk)) ≥ Ω(k ⋅ Rpubε(f)) \enspace, where fk= f × … × f (k-times) and Rpubε(⋅) represents the public-coin randomized communication complexity with worst-case error ε. Given a protocol P for fk with communication cost c ⋅ k and worst-case error ε, we exhibit a protocol Q for f with external-information-cost O(c) and worst-error ε. We then use a message compression protocol due to Barak, Braverman, Chen and Rao [2013] for simulating Q with communication O(c ⋅ log(c⋅ k)) to arrive at our result. To show this reduction we show some new chain-rules for capacity, the maximum information that can be transmitted by a communication channel. We use the powerful concept of Nash-Equilibrium in game-theory, and its existence in suitably defined games, to arrive at the chain-rules for capacity. These chain-rules are of independent interest.