Domanda

Devo dimostrarlo $ Disc_ mu (disj) geq frac {1} {2n+1} $ per qualsiasi distribuzione $ mu: {0,1 }^n Times {0,1 }^n a [0,1] $. La disgiunzione è definita come

$ Disj (x, y) = left { inizio {array} [ll] +1 & text {if $ x cap y = vuoto $} 0 & text {altrimenti} end {array } a destra. $

La discrepanza per una funzione è definita come $ Disc_ mu (f) = max_r {disc_ mu (r, f) } $ su tutti i rettangoli $ R $ e inoltre

$$ 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] |. $$

Non capisco dove il $ frac {1} {2n+1} $ viene da e come definire un rettangolo adeguato $ R $.

Il problema è dato come esercizio senza una soluzione nel libro Complessità comunicativa Di E. Kushilevitz e N. Nisan a pagina 40.

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top