Limite supérieure pour la disjointure définie sous distributions de produits

Question

Pour le problème de disjointure défini dans le modèle de complexité de la communication à 2 partis, ALICE reçoit une entrée $ x $ et bob reçoit une entrée $ y $ , $ x $ et $ y $ sont < SPAN CLASS="MATH-CONTENEUR"> N $ N $ -LENDENDS DE LONGRESSE (échantillonnés de certaines distributions), qui sont interprétés comme sous-ensembles de $ [n] $ ,, $ x_i= 1 $ désigne la $ i $ -th bit de $ x $ est dans le sous-ensemble. L'objectif est destiné à Alice et Bob de répondre si les sous-ensembles représentés par $ x $ et $ y $ sont disjoint en utilisant aussi peu de communication que possible. Il est connu que $ \ oméga (n) $ est nécessaire dans le pire des cas pour les protocoles randomisés.

Je suis tombé sur ce brouillon du manuel Complexité de communication de ANUP RAO et Amir Yehudayoff , où l'exercice 6.8 mentionne que la disjointure de 2 partis peut être résolue avec un numéro attendu de $ o (n ^ {2 / 3} \ log ^ 2 n) $ bits si les entrées d'Alice et de Bob sont échantillonnées indépendamment.

Considérez le protocole suivant. S'il y a une coordonnée $ j \ in [n] $ telle que $ h (x_j) $ et $ h (y_j) $ est à la fois au moins $ \ epsilon $ , puis alice et bob communiquer $ x_j, y_j $ . Ils affectent les valeurs qu'ils voient et répètent cette étape jusqu'à ce qu'aucune coordonnée de ce type ne puisse être trouvée. À ce stade, Alice et Bob utilisent le théorème de codage de Shannon pour coder $ x $ , $ y $ . Montrer comment définir $ \ EPSILON $ de sorte que la communication attendue puisse être limitée par $ n ^ {2/3} \ log ^ 2 N $ . Astuce: utilisez le fait que $ h (x_j) \ ge \ epsilon $ implique que $ pr [x_j= 1] \ GE \ OMEGA (\ epsilon / (\ journal (1 / ε))) $ .

Je suppose que l'idée est d'abord de communiquer tous les indices où $ x $ et $ ont Grande entropie, puis utiliser le fait que les indices restants doivent avoir une petite entropie. Cependant, les détails du protocole et où l'indépendance de $ x $ et $ y $ arrive , n'est pas clair pour moi.

Answer 1

Au cours de la première phase de l'algorithme, les joueurs zooment sur une coordonnée à entrouvert. Ils échangent $ O (1) $ bits et arrêtent à chaque étape avec une probabilité $ \ omega (\ epsilon ^ 2 / \ journal ^ 2 (1 / \ epsilon)) $ (ici nous utilisons l'indépendance). Par conséquent, cette phase utilise au plus $ o (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2) $ bits dans l'attente. La deuxième phase utilise $ o (n \ epsilon) $ bits. Au total, nous avons utilisé ces nombreux bits dans l'attente: $$ O (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2 + \ epsilon n). $$ Choisissez $ \ epsilon= 1 / n ^ {1/3} $ pour obtenir la liaison indiquée.

Sans indépendance, nous n'avons aucun contrôle sur la probabilité d'arrêt à chaque étape de la première phase. Par exemple, il pourrait être que $ x $ est échantillonné uniformément au hasard et $ y $ est le négation de $ x $ . Dans ce cas, la première phase ne s'arrêtera jamais, et le protocole utilisera donc toujours $ 2n $ $ bits.

comme un de côté, la limite supérieure peut être améliorée à $ o (\ sqrt {n} \ journal n) $ , qui correspond presque à la limite inférieure $ \ oméga (\ sqrt {n}) $ (l'écart aurait pu être fermé dans la littérature). Voir Notes de conférence de Prahladh Harsha | / a>.