Las Vegas vs Monte Carlo complexité de l'arbre de décision aléatoire

Contexte:

La complexité de l'arbre de décision ou la complexité des requêtes est un modèle de calcul simple défini comme suit. Soit $f:\{0,1\}^n\to \{0,1\}$ une fonction booléenne. La complexité de requête déterministe de $f$ , notée $D(f)$ , est le nombre minimum de bits de l'entrée $x\in\{0,1\}^n$ qui doivent être lus (dans le pire des cas) par un algorithme déterministe qui calcule $f(x)$. Notez que la mesure de la complexité est le nombre de bits de l'entrée qui sont lus; tous les autres calculs sont gratuits.

De même, nous définissons la complexité de requête randomisée de Las Vegas de , notée R 0 ( f ) , comme le nombre minimum de bits d'entrée qui doivent être lus dans l'attente par un algorithme randomisé sans erreur qui calcule f ( x ) . Un algorithme sans erreur génère toujours la bonne réponse, mais le nombre de bits d'entrée lus par celui-ci dépend du caractère aléatoire interne de l'algorithme. (C'est pourquoi nous mesurons le nombre attendu de bits d'entrée lus.)$f$$R_0(f)$$f(x)$

Nous définissons la complexité de requête randomisée Monte Carlo de , notée R 2 ( f ) , comme le nombre minimum de bits d'entrée qui doivent être lus par un algorithme randomisé à erreur bornée qui calcule f ( x ) . Un algorithme d'erreur limitée génère toujours une réponse à la fin, mais il n'a besoin que d' être correct avec une probabilité supérieure à 2 / 3 ( par exemple).$f$$R_2(f)$$f(x)$$2/3$

Question

Que sait-on de la question de savoir si

?$R_0(f) = \Theta(R_2(f))$

Il est connu que

$R_0(f) = \Omega(R_2(f))$

parce que les algorithmes de Monte Carlo sont au moins aussi puissants que les algorithmes de Las Vegas.

J'ai récemment appris qu'il n'y a pas de séparation connue entre les deux complexités. La dernière référence que je puisse trouver pour cette affirmation date de 1998 [1]:

[1] Nikolai K. Vereshchagin, Randomized Boolean decision trees: Plusieurs remarques, Theoretical Computer Science, Volume 207, Numéro 2, 6 novembre 1998, Pages 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

La limite supérieure la plus connue de l'un en termes de l'autre est

$R_0(f) = O(R_2(f)^2 \log{R_2(f)})$

en raison de [2]:

[2] Kulkarni, R. et Tal, A. (2013, novembre). Sur la sensibilité au bloc fractionnaire. Dans Electronic Colloquium on Computational Complexity (ECCC) (Vol. 20, p. 168).

J'ai deux questions précises.

1. [Demande de référence]: Existe-t-il un document plus récent (après 1998) qui traite de ce problème?
2. Plus important encore , existe-t-il une fonction candidate qui est conjecturée pour séparer ces deux complexités?

Ajouté en v2: Ajouté ref [2], a souligné la deuxième question sur l'existence de la fonction candidate.

Pour autant que je sache, cela est toujours ouvert. Un article très récent qui mentionne ces quantités et certaines limites est Aaronson et al: Faible parité (voir http://arxiv.org/abs/1312.0036 ). Vous pouvez également voir le chapitre 14 de Jukna: Boolean funcions et l'enquête de 1999 (bat toujours 1998!) De Buhrman et de Wolf. Un autre article très récent sur la complexité de l'arbre de décision randomisé est Magniez et al: http://arxiv.org/abs/1309.7565

Enfin, un petit résumé que je me suis fait le mois dernier (sans defs):

R2 <= R0 <= D <= n

D <= N0 * N1 <= C ^ 2 <= R0 ^ 2

s <= bs <= C <= s * bs <= bs ^ 2 (nouveau: [Gilmer-Saks-Srinivasan]: il y a f st bs ^ 2 (f) = O (C (f)))

D <= N1 * bs <= bs ^ 3 <= (3R2) ^ 3

deg <= D <= bs * deg <= deg ^ 3 (nouveau: [Tal]: bs <= deg ^ 2)

D <= N1 * deg

C <= bs * deg ^ 2 <= deg ^ 4

La conjecture de sensibilité est que s est également polynomialement lié à d'autres paramètres.

Cette question a été résolue!

$f$

$R_0(f) = \tilde{\Omega}(R_2(f)^{2})$

et même

$R_0(f) = \tilde{\Omega}(R_1(f)^{2})$

$R_1(f)$

Les deux séparations sont optimales jusqu'aux facteurs de log!