Completezza della comunicazione per le distribuzioni dei prodotti

Question

In generale per il problema di disgiunzione del set (a due partite) per gli input di lunghezza n, sappiamo che le parti devono comunicare $ \ omega (n) $ . Sorprendentemente, oggi ho scoperto (se ho capito correttamente) che questo non è vero per le distribuzioni di prodotti, cioè quando gli input di Alice e Bob sono scelti indipendentemente dalle distribuzioni arbitrarie! In questo carta , ad esempio, forniscono un limite superiore con complessità della comunicazione $ \ mathcal {o} (\ sqrt {n}} (1 / \ epsilon)) $ , dove $ \ Epsilon $ è un termine di errore non rilevante per la domanda qui. Ora sono curioso che esistano le lacune per altri problemi di complessità della comunicazione ben noti.

Domanda: Quali altri problemi noti esibiscono un divario tra le complessità di comunicazione quando si considera distribuzioni di ingressi arbitrari e distribuzioni di prodotti. Ci sono risultati simili per prodotti interni o intersezioni?

Answer 1

Set Disjointness è più facile per le distribuzioni dei prodotti poiché la distribuzione rigida per la disgiunta disgiunta è molto lontana dall'essere una distribuzione del prodotto. Cosa necessifichiamo da una distribuzione rigida $ (x, y) $ per il prodotto interno? Vogliamo ognuna delle $ x, y $ separatamente per essere piuttosto casuale, e vogliamo $ x \ clot y $ Per essere per lo più zero, dire $ x \ cdot y $ contiene al massimo una singola classe $ 1 $ . Questo non può essere ottenuto da una distribuzione del prodotto. Mentre puoi ottenere la $ x \ clot y $ proprietà, ciò implica che ciascuno dei due ingressi sarà molto prevenuto. Viceversa, se gli ingressi $ x, y $ sono abbastanza casuali, quindi $ x \ cdot y $ avere molte $ 1 $ s

La funzione del prodotto interno non soffre dello stesso problema. In effetti, sembra che la distribuzione più difficile sia la distribuzione uniforme. È possibile dimostrare un limite inferiore lineare utilizzando il metodo di discrepanza - questo è standard e utilizza un limite sulla discrepanza nota come Lindsey's Lemma .

Sherstv ha trovato un esempio di gapi ottimale nel suo documento Complessità di comunicazione sotto distribuzione di prodotti e non prodotti . La sua funzione è una funzione casuale, scelta in modo che non ci siano grandi grandi class monocromatiche="container per la matematica"> $ 1 $ -rectnicles. Il risultato finale è una funzione la cui complessità della comunicazione randomizzata è $ \ omega (n) $ , ma per qualsiasi distribuzione del prodotto, la complessità della comunicazione randomizzata è $ o (1) $ .