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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top