Complexité de communication déterministe vs numéro de partition

Contexte:

Considérons le modèle habituel à deux parties de la complexité de la communication où Alice et Bob reçoivent des chaînes de $n$ bits $x$ et $y$ et doivent calculer une fonction booléenne $f(x,y)$ , où $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ .

Nous définissons les quantités suivantes:

$D(f)$ (la complexité de communication déterministe de): le nombre minimum de bits que Alice et Bob doivent communiquer pour calculerdéterministe.f ( x , y $f$$f(x,y)$

$Pn(f)$ (le numéro de partition de ): le logarithme (base 2) du plus petit nombre de rectangles monochromes dans une partition (ou une couverture disjointe) de .{ 0 , 1 } n × { 0 , 1 } $f$$\{0,1\}^n \times \{0,1\}^n$

Un rectangle monochromatique dans est un sous-ensemble tel que prend la même valeur (c'est-à-dire est monochromatique) sur tous les éléments de . R × C f R × $\{0,1\}^n \times \{0,1\}^n$$R \times C$$f$$R \times C$

A noter également que le numéro de partition est différent du "numéro de partition de protocole", qui faisait l'objet de cette question .

Voir le texte de Kushilevitz et Nisan pour plus d'informations. Dans leur notation, ce que j'ai défini comme est .log 2 C D ( f $Pn(f)$$\log_2 C^D(f)$

Remarque : Ces définitions sont facilement généralisées aux fonctions non booléennes , où la sortie de est un ensemble plus grand.$f$$f$

Résultats connus:

On sait que est une borne inférieure sur , c'est-à-dire pour tous (booléens ou non-booléens) , . En effet, la plupart des techniques de borne inférieure (ou peut-être toutes?) Pour fait des inférieures . (Quelqu'un peut-il confirmer que cela est vrai pour toutes les techniques de limite inférieure?)D ( f ) f P n ( f ) ≤ D ( f ) D ( f ) P n ( f $Pn(f)$$D(f)$$f$$Pn(f) \leq D(f)$$D(f)$$Pn(f)$

On sait également que cette borne est tout au plus quadratique (pour les fonctions booléennes ou non-booléennes), c'est-à-dire . Pour résumer, nous savons ce qui suit:$D(f) \leq (Pn(f))^2$

$Pn(f) \leq D(f) \leq (Pn(f))^2$

On suppose que . (C'est le problème ouvert 2.10 dans le texte par texte de Kushilevitz et Nisan.) Cependant, à ma connaissance, la séparation la plus connue entre ces deux pour les fonctions booléennes n'est que par un facteur multiplicatif de 2, comme indiqué dans "The La conjecture de réseau linéaire dans la complexité de la communication est fausse "par Eyal Kushilevitz, Nathan Linial et Rafail Ostrovsky.$Pn(f) = \Theta(D(f))$

Plus précisément, ils présentent une famille infinie de fonctions booléennes , telles que .D ( f ) ≥ ( 2 - o ( 1 ) ) P n ( f $f$$D(f) \geq (2 - o(1)) Pn(f)$

Question:

Quelle est la séparation la plus connue entre et pour les fonctions non booléennes? S'agit-il toujours de la séparation du facteur 2 mentionnée ci-dessus?D ( f $Pn(f)$$D(f)$

Ajouté en v2 : comme je n'ai pas reçu de réponse depuis une semaine, je suis également heureux d'entendre des réponses partielles, des conjectures, des ouï-dire, des preuves anecdotiques, etc.

Cette question vient d'être résolue! Comme je l'ai mentionné, on savait que

,$Pn(f) \leq D(f) \leq (Pn(f))^2$

mais c'était un problème ouvert majeur de montrer que ou qu'il existe une fonction pour laquelle P n ( f ) = o ( D ( f ) ) .$Pn(f) = \Theta(D(f))$$Pn(f) = o(D(f))$

Il y a quelques jours, cela a été résolu par Mika Göös, Toniann Pitassi, Thomas Watson ( http://eccc.hpi-web.de/report/2015/050/ ). Ils montrent qu'il existe une fonction qui satisfait$f$

.$Pn(f) = \tilde{O}((D(f))^{2/3})$

Ils montrent également un résultat optimal pour la version unilatérale de , que je désignerai par P n 1 ( f ) , où il suffit de couvrir les entrées 1 avec des rectangles. P n 1 ( f ) satisfait également $Pn(f)$$Pn_1(f)$$Pn_1(f)$

,$Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$

et ils montrent que c'est la meilleure relation possible entre les deux mesures, car ils présentent une fonction qui satisfait$f$

.$Pn_1(f) = \tilde{O}((D(f))^{1/2})$

Vous remarquez que les bornes inférieures de sont étroitement liées à toutes les techniques existantes de borne inférieure. Pour les fonctions booléennes, cela semble vrai, tant que la conjecture du log-rank est vraie. Cependant, P n ( f ) peut être exponentiellement plus grand que l'ensemble de tromper lié.$Pn(f)$$Pn(f)$

Il n'est pas clair pour moi combien et D ( f ) peuvent différer dans le cas non booléen.$Pn(f)$$D(f)$

Dans le reste, je précise ces commentaires.

KN (Kushilevitz et Nisan dans leur manuel de 1997) décrivent les trois techniques de base pour les fonctions booléennes: la taille d'un ensemble de dupes, la taille d'un rectangle monochromatique et le rang de la matrice de communication.

Tout d'abord, tromper les ensembles. Un ensemble de tromper est monochromatique: il y a une certaine z ∈ { 0 , 1 } de telle sorte que f ( x , y ) = z pour chaque ( x , y ) ∈ S . Un patch final est alors nécessaire pour prendre en compte l'autre couleur. Cette étape supplémentaire peut être évitée. Soit f : X × Y → { 0 , 1 } une fonction. Une paire d'éléments distincts ( x 1$S$$z \in \{0,1\}$$f(x,y) = z$$(x,y)\in S$$f \colon X \times Y \to \{0,1\}$ estduper faiblementpour f si f ( x 1 , y 1 ) = f ( x 2 , y 2 ) implique que soit f ( x 1 , y 2 ) ≠ f ( x 1 , y 1 ) ou f $(x_1,y_1),(x_2,y_2) \in X \times Y$$f$$f(x_1,y_1) = f(x_2,y_2)$$f(x_1,y_2) \ne f(x_1,y_1)$ . Un ensemble S ⊆ X × Y est unensemble de duperie faiblepour f si chaque paire distincte d'éléments de S trompe faiblement. KN indique implicitement après la preuve de 1,20 que la taille du journal d'un ensemble de duperie faible est une limite inférieure pour la complexité de la communication.$f(x_2,y_1) \ne f(x_1,y_1)$$S \subseteq X \times Y$$f$$S$

Un plus grand jeu de duperie faible choisit un élément représentatif de chaque rectangle monochromatique dans un plus petit couvercle de jeu disjoint. La taille d'un plus grand ensemble de tromperie faible est donc au plus aussi grande que (l'exposant de) le numéro de partition. Malheureusement, la limite fournie par les ensembles de tromperie est souvent faible. La preuve de KN 1.20 montre que toute fonction mappant chaque élément d'un ensemble de duperie faible S à un rectangle monochromatique R s contenant cet élément est injective. Cependant, il peut y avoir de nombreux rectangles monochromes R dans une couverture disjointe la plus petite qui n'apparaissent pas dans l'image de S , chaque élément de R trompant faiblement certains mais pas tous les éléments de$s$$S$$R_s$$R$$S$$R$ , et ne peut donc pas être simplement ajouté à S . En fait Dietzfelbinger, Hromkovič et Schnitger montré (doi:10.1016 / S0304-3975 (96) 00062-X) que pour tout assez grand n , au moins 1 / 4 de toutesfonctions booléennes sur les n variables ont des P n ( f ) = n ont encore (faibles) des ensembles trompeurs de taille de journal O ( log n ) . Ainsi, le journal de la taille d'un ensemble de tromperie le plus grand (faible) peut être exponentiellement plus petit que la complexité de la communication.$S$$S$$n$$1/4$$n$$Pn(f) = n$$O(\log n)$

Pour le rang, établir une correspondance étroite entre le rang de la matrice de la fonction et son numéro de partition établirait une forme de conjecture log-rang (en fonction de l'étroitesse de la correspondance). Par exemple, s'il existe une constante telle que P n ( f ) ≤ un log r k ( f ) pour chaque fonction booléenne f , alors D ( f ) ≤ ( 2 un log r k ( f ) ) $a> 0$$Pn(f) \le a\log rk(f)$$f$$D(f) \le (2a\log rk(f))^2$, et une sorte de conjecture de log-rang s'applique alors aux familles de fonctions pour lesquelles augmente finalement avec | X | + | Y | , avec exposant 2 + ϵ pour tout ϵ > 0 réalisable pour suffisamment grand | X | + | Y | . (Rappelons que la conjecture de log-rank de Lovász-Saks dit qu'il y a une constante c > 0 telle que D ( f ) ≤ ( log $rk(f)$$|X|+|Y|$$2+\epsilon$$\epsilon > 0$$|X|+|Y|$$c>0$ pour chaque fonction booléenne f ; ici r k ( f ) est le rang de la matrice de communication de f sur les réels.)$D(f) \le (\log rk(f))^c$$f$$rk(f)$$f$

De même, s'il n'y a qu'un seul grand rectangle monochromatique avec de nombreux petits, le numéro de partition donne une limite plus forte que la taille logarithmique d'un plus grand rectangle monochromatique. Cependant, la conjecture log-rank est également équivalente à une conjecture sur la taille d'un plus grand rectangle monochromatique (Nisan et Wigderson 1995, doi: 10.1007 / BF01192527 , Théorème 2). Ainsi, l'utilisation de rectangles monochromes n'est pas actuellement connue pour être "identique à" l'utilisation du numéro de partition, mais ils sont étroitement liés si la conjecture de log-rank est vraie.

En résumé, la taille du journal d'un plus grand ensemble de tromperie faible peut être exponentiellement plus petite que le numéro de partition. Il peut y avoir des écarts entre les autres techniques de limite inférieure et le nombre de partitions, mais si la conjecture de log-rank est vraie, ces écarts sont faibles.

En utilisant des notions de taille qui s'étendent à l'ordinaire (de cardinalité), la taille de tout rectangle monochromatique peut être utilisée pour généraliser les ensembles de duperie et pour réduire la complexité de la communication (voir KN 1.24). Je ne sais pas à quel point la plus grande "taille" généralisée d'un rectangle monochromatique doit être proche de la complexité de la communication.

Contrairement à la discussion ci-dessus pour les fonctions booléennes, pour les fonctions non booléennes, l'écart entre et log r k ( f ) peut être exponentiel. KN 2.23 donne un exemple: soit f la fonction qui renvoie la taille des intersections des ensembles représentés par les deux vecteurs caractéristiques d'entrée. Pour cette fonction, le log-rank est log n . Maintenant, l'ensemble de toutes les paires d'ensembles sans intersection a 3 n éléments. Autant que je sache, il ne peut y avoir de rectangles monochromes plus grands que cet ensemble. Si cela est correct, alors D ( f ) $D(f)$$\log rk(f)$$f$$\log n$$3^n$ , donc pour cette fonction, D ( f ) , P n ( f ) et la taille logarithmique d'un plus grand rectangle monochromatique sont tous dans un facteur d'au plus 2,5 de l'autre, toutétant loin de façon exponentiellerang de journal. D'où de petites séparations entre P n ( f ) et D ( f $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$$D(f)$$Pn(f)$$2.5$$Pn(f)$$D(f)$peut être possible dans le cas non booléen, mais ils ne sont pas liés de manière évidente au log-rang de la matrice de . Je n'ai connaissance d'aucun travail publié sur la manière dont ces mesures sont liées dans le cas non booléen.$f$

Enfin, Dietzfelbinger et al. a également défini un ensemble étendu de tromperie lié, généralisant la condition de tromperie à partir de paires (sous-ensembles «d'ordre 1») vers des sous-ensembles plus grands d'éléments monochromatiques; la condition de duper étendue nécessite que la sous-matrice couverte par les éléments monochromatiques ne soit pas monochromatique. Il n'est pas clair comment cela se comporte lorsque l'ordre des sous-ensembles monochromatiques augmente, car il faut diviser la taille de la tromperie étendue définie par l'ordre et considérer la plus grande valeur sur tous les ordres. Cependant, cette notion finit par être une borne inférieure proche de .$Pn(f)$