ECCC-Report TR18-175https://eccc.weizmann.ac.il/report/2018/175Comments and Revisions published for TR18-175en-usTue, 15 Jan 2019 15:06:25 +0200
Revision 2
| Lifting Theorems for Equality |
Bruno Loff,
Sagnik Mukhopadhyay
https://eccc.weizmann.ac.il/report/2018/175#revision2We 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 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 \cdot n)$.Tue, 15 Jan 2019 15:06:25 +0200https://eccc.weizmann.ac.il/report/2018/175#revision2
Revision 1
| Lifting Theorems for Equality |
Bruno Loff,
Sagnik Mukhopadhyay
https://eccc.weizmann.ac.il/report/2018/175#revision1We 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)$.Tue, 30 Oct 2018 23:49:38 +0200https://eccc.weizmann.ac.il/report/2018/175#revision1
Paper TR18-175
| Lifting Theorems for Equality |
Bruno Loff,
Sagnik Mukhopadhyay
https://eccc.weizmann.ac.il/report/2018/175We 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)$.Tue, 23 Oct 2018 16:57:01 +0300https://eccc.weizmann.ac.il/report/2018/175