Legato superiore per il set disgiunta sotto le distribuzioni dei prodotti

Question

Per il problema del disgiuntamento del set nel modello di 2 partito della complessità della comunicazione, Alice viene assegnato un ingresso $ x $ e Bob è dato input $ y $ , $ x $ e $ y $ sono < Span Class="Math-Container"> $ N $ -length Bitstrings (campionati da qualche distribuzione), che sono interpretati come sottoinsiemi di $ [n] $ , cioè, $ x_i= 1 $ indica la $ I $ -th bit di $ x $ è nel sottoinsieme. L'obiettivo è per Alice e Bob per rispondere se i sottoinsiemi rappresentati da $ x $ e $ y $ sono disgiunti usando la minima comunicazione possibile. È noto che $ \ omega (n) $ i bit sono necessari nel peggiore dei casi per protocolli randomizzati.

Mi sono imbattuto in questa bozza del libro di testo complessità della comunicazione di ANUP RAO e Amir Yehudayoff , dove l'esercizio 6.8 menziona che il set di set di 2 partito può essere risolto con un numero previsto del numero di $ o (n ^ {2 / 3} \ log ^ 2 n) $ bit se gli ingressi di Alice e Bob sono campionati in modo indipendente.

.

Considera il seguente protocollo. Se c'è una coordinata $ j \ in [n] $ in modo tale che $ h (x_j) $ e $ h (y_j) $ sono entrambi almeno $ \ epsilon $ , allora Alice e Bob comunicano $ x_j, y_j $ . Condiziona i valori che vedono e ripetono questo passaggio fino a quando non si possono trovare una coordinata di questo tipo. A questo punto, Alice and Bob utilizza il teorema della codifica di Shannon per codificare $ x $ , $ y $ . Mostra come impostare $ \ Epsilon $ in modo che la comunicazione prevista possa limitata da $ n ^ {2/3} \ log ^ 2 N $ . Suggerimento: usa il fatto che $ h (x_j) \ ge \ epsilon $ implica che $ PR [x_j= 1] \ Ge \ Omega (\ Epsilon / (\ log (1 / ε))) $ .

Suppongo che l'idea sia quella di comunicare prima tutti gli indici in cui $ x $ e $ y $ HAVE Grande entropia e quindi utilizzare il fatto che gli indici rimanenti devono avere una piccola entropia. Tuttavia, i dettagli del protocollo e dove l'indipendenza della classe $ x $ e $ y $ sta arrivando , non sono chiaro a me.

Answer 1

Durante la prima fase dell'algoritmo, i giocatori ingrandiscono una coordinata ad alta entropia. Scambio $ o (1) $ bit e fermati ad ogni passaggio con probabilità $ ^ 2 / \ log ^ 2 (1 / \ epsilon)) $ (qui usiamo l'indipendenza). Quindi questa fase si rivolge al massimo $ o (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2) $ bit in attesa. La seconda fase utilizza $ o (n \ epsilon) $ bit. In totale, abbiamo usato questo molti bit in attesa: $$ O (\ log ^ 2 (1 / \ Epsilon) / \ epsilon ^ 2 + \ epsilon n). $$ Scegli $ \ epsilon= 1 / n ^ {1/3} $ per ottenere il limite dichiarato.

Senza indipendenza, non abbiamo alcun controllo sulla probabilità di arresto in ogni fase della prima fase. Ad esempio, potrebbe essere che $ x $ viene campionato uniformemente a caso e $ y $ è il negazione di $ x $ . In questo caso la prima fase non si fermerà mai, e quindi il protocollo utilizzerà sempre $ 2N $ bit.

In quanto a parte, il limite superiore può essere migliorato a $ o (\ sqrt {n} \ log n) $ , che quasi corrisponde al limite inferiore < class="container math"> $ \ omega (\ sqrt {n}) $ (il gap potrebbe essere stato chiuso in letteratura). Vedi Lezioni note di Prahladh Harsha < / a>.