Lower bound of disjointness by discrepancy?
-
05-11-2019 - |
Frage
I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$. Disjointness is defined as
$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$
The discrepancy for a function is defined as $Disc_\mu(f) = \max_R \{Disc_\mu(R,f)\}$ over all rectangles $R$ and further
$$Disc_\mu(R,f) = |\Pr_\mu [(x,y) \in R \wedge f(x,y)=1] - \Pr_\mu[(x,y) \in R \wedge f(x,y) =0] |.$$
I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.
The problem is given as an exercise without a solution in the book Communication Complexity by E. Kushilevitz and N. Nisan on page 40.
Keine korrekte Lösung