Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-175 | 30th October 2018 23:49

Lifting Theorems for Equality

RSS-Feed




Revision #1
Authors: Bruno Loff, Sagnik Mukhopadhyay
Accepted on: 30th October 2018 23:49
Downloads: 19
Keywords: 


Abstract:

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ 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\circ EQ_n$ is $\Omega(deg(f) \cdot 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 \circ EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ EQ_n$ is at least $D(f) \cdot 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 the first tight lower-bound for the deterministic communication complexity of the natural Gap-Equality problem, where Alice and Bob are each given $p$-many $n$-bit strings, with the promise that either $\frac{3}{4}$ of them are equal or $\frac{3}{4}$ of them are different, and they wish to know which is the case. We show that the complexity of this problem is $\Theta(p \cdot n)$.



Changes to previous version:

Fixed a few typographical errors.


Paper:

TR18-175 | 23rd October 2018 16:43

Lifting Theorems for Equality


Abstract:

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ 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\circ EQ_n$ is $\Omega(deg(f) \cdot 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 \circ EQ_n$ has communication complexity $O(n)$. Nonetheless, we are able to show that the communication complexity of $f \circ EQ_n$ is at least $D(f) \cdot 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 the first tight lower-bound for the deterministic communication complexity of the natural Gap-Equality problem, where Alice and Bob are each given $p$-many $n$-bit strings, with the promise that either $\frac{3}{4}$ of them are equal or $\frac{3}{4}$ of them are different, and they wish to know which is the case. We show that the complexity of this problem is $\Theta(p \cdot n)$.



ISSN 1433-8092 | Imprint