On the Power of Laconic Advice in Communication Complexity

摘要

We continue the study of a recently introduced model of communication complexity with advice, focusing on the power of advice in the context of equality of bitstrings and divisibility of natural numbers. First, we establish that the equality problem admits a protocol of poly-logarithmic communication, provided a laconic advice of just one bit. For the divisibility problem, we design a protocol with sublinear communication and advice of roughly O(n~(1/2)). We complement our result on divisibility with a matching lower bound in a restricted setting using a recent result of Chattopadhyay et al. and a reduction from set-disjointness to divisibility.