Abstract
We show a deterministic simulation (or lifting) theorem for composed problems f o Eq_n where the inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to show via a rank argument that the communication complexity of f o Eq_n is Omega(deg(f) * n). However, there is a surprising counterexample of a partial function f on p bits, such that any completion f' of f has deg(f') = Omega(p), and yet f o Eq_n has communication complexity O(n). Nonetheless, we are able to show that the communication complexity of f o Eq_n is at least D(f) * n for a complexity measure D(f) which is closely related to the ANDquery complexity of f and is lowerbounded by the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the setdisjointness gadget, and a lifting theorem in the context of parity decisiontrees, for the NOR gadget.
As an application, we prove a tight lowerbound for the deterministic communication complexity of the communication problem, where Alice and Bob are each given pmany nbit strings, with the promise that either all of the strings are distinct, or allbutone of the strings are distinct, and they wish to know which is the case. We show that the complexity of this problem is Theta(p * n).
BibTeX  Entry
@InProceedings{loff_et_al:LIPIcs:2019:10289,
author = {Bruno Loff and Sagnik Mukhopadhyay},
title = {{Lifting Theorems for Equality}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {50:150:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10289},
doi = {10.4230/LIPIcs.STACS.2019.50},
annote = {Keywords: Communication complexity, Query complexity, Simulation theorem, Equality function}
}
Keywords: 

Communication complexity, Query complexity, Simulation theorem, Equality function 
Collection: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) 
Issue Date: 

2019 
Date of publication: 

12.03.2019 