Complexité de communication aléatoire sans erreur vs complexité de communication déterministe

Il est connu que pour l' erreur , la pire définition de cas de complexité de communication aléatoire et la définition de cas moyenne sont équivalentes. Mais lorsque l'erreur est , la pire complexité de communication aléatoire est la même que la complexité de communication déterministe. $\Theta(1)$ $0$

Une fonction est-elle connue pour avoir une complexité de communication déterministe super-constante mais une complexité de communication aléatoire à erreur nulle constante?

Plus généralement, qu'est-ce qu'une fonction témoin qui sépare la complexité de la communication déterministe et la complexité de la communication randomisée sans erreur?

Toute aide est appréciée.

communication-complexity sagnik
la source

Vous voulez dire le contraire (petit randomisé, mais grand déterministe)?

Noam

Oui, extrêmement désolé pour ce gâchis. Je veux une complexité de communication aléatoire à erreur constante mais une complexité de communication déterministe super constante. Je cherchais le problème de la disjonction set. Comme et le protocole Hastad-Wigderson donne déjà un protocole unilatéral pour la disjonction set de coût le problème se résume à prouver une limite supérieure unilatérale d'erreur bornée à coût constant pour la non-k-set-disjointness. Y a-t-il déjà un résultat?

k

$k$

R_{0} (f) = O (m a x {R^{1} (f), R^{1} (not f)})

$R_0(f)=O(max\{R^1(f), R^1(\text{not }f)\})$

k

$k$

O (k)

$O(k)$

sagnik

Réponses:

En effet, pour la distanciation d'ensembles de taille sur éléments, il est connu que la complexité de communication aléatoire à est , tandis que la complexité déterministe est . $\log(n)$ $n$ $0$ $\Theta(\log n)$ $\Theta(\log^2 n)$

Rappelons qu'il peut y avoir au plus un écart quadratique puisque la complexité randomisée à erreur est limitée par le bas par les complexités non déterministes et co-non déterministes. $0$

Voir: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf

Noam
la source

Merci beaucoup. Cela répond parfaitement à ce que je veux savoir.

sagnik

Désolé, je vais le faire.

2014