2026-07-25T03:14:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10289 2024-03-06T10:45:43Z ddc:004 open_access

Lifting Theorems for Equality Loff, Bruno Mukhopadhyay, Sagnik Communication complexity Query complexity Simulation theorem Equality function 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 counter-example 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 AND-query complexity of f and is lower-bounded by the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR gadget. As an application, we prove a tight lower-bound for the deterministic communication complexity of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the promise that either all of the strings are distinct, or all-but-one 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno Loff and Sagnik Mukhopadhyay 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.50 urn:nbn:de:0030-drops-102892 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.50 eng https://creativecommons.org/licenses/by/3.0/legalcode