A note on the partition bound for one-way classical communication complexity

2023/02/21 by Srinivasan Arunachalam, Arunachalam, Srinivasan, João F. Doriguello +3
Computer Science · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2302.10431

Abstract

We present a linear program for the one-way version of the partition bound (denoted prt¹_ε(f)). We show that it characterizes one-way randomized communication complexity R_ε¹(f) with shared randomness of every partial function f:X\timesY\toZ, i.e., for δ,ε∈(0,1/2), R_ε¹(f) ≥ \logprt_ε¹(f) and R_ε+δ¹(f) ≤ \logprt_ε¹(f) + loglog(1/δ). This improves upon the characterization of R_ε¹(f) in terms of the rectangle bound (due to Jain and Klauck, 2010) by reducing the additive O(log(1/δ))-term to loglog(1/δ).

Related

• Pseudodeterministic Communication Complexity
• Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound
• Rectangle Size Bounds and Threshold Covers in Communication Complexity
• The Partition Bound for Classical Communication Complexity and Query Complexity
• Communication Complexity