Fractional Covers and Communication Complexity (Extended Abstract)
Mauricio Karchmer, Eyal Kushilevitzt, Noam Nisant · 1992
29.54> (H 2 f \\Thetag ; D 1 ) N (H 2 f \\Theta H 2 g ; D 1 \\Theta D 1 ) is similar to the proof of Theorem 2.4 (first direction), together with the second part of Lemma 4.3 that guarantees that D 1 (e) = D 1 (e f ) \\Delta D 1 (e g ). Using the last two theorems, we get D(H 2 f ; D 1 ) \\Delta D(H 2 g ; D 1 ) D(H 2 f \\Thetag ; D 1 ) D(H 2 f ; D 1 )