Amplifier l'exactitude des algorithmes $ mathsf {rp} $ utilisant des graphiques d'expander

Question

Un graphique $ g = (v, e) $ est appelé $ (n, d, varepsilon) $ -extenseur Si le graphique a $ n $ sommets, le degré maximum $ d $ et satisfaire ce qui suit propriété d'extension:

• pour chaque sous-ensemble $ w sous-ensemble v $ tel que $ | w | leq n / 2 $, $ | w cup n (w) | ge (1+ varepsilon) | w | $

où $ n (w) $ est le quartier de $ w $ en $ g $. La propriété d'extension signifie, de manière informelle, que le quartier de $ W $ est "grand" lorsque $ w $ est "petit". Selon lequel des expanseurs existent peuvent être montrés avec la méthode probabiliste (voir, par exemple, ce Rédaction d'Ellis).

J'essaie de montrer que les expanseurs peuvent être utilisés pour amplifier la probabilité de succès des algorithmes Monte Carlo unilatéraux. En particulier, étant donné un algorithme de temps polynomial $ un $ pour un problème dans Rp qui utilise $ n $ bits aléatoires et donne de faux négatifs avec probabilité au plus 1/2 $ que nous voulons montrer qu'il existe un algorithme de temps polynomial qui utilise $ n $ bits aléatoires et donne des faux négatifs avec une probabilité au plus $ n ^ {- c } $ pour une constante fixe $ c $.

Voici la méthode qu'on m'a demandé d'analyser. Nous considérons $ a $ comme une fonction $ a (x, r) $ où $ x $ est l'entrée et $ r $ est une chaîne représentant les bits aléatoires. Sur l'entrée $ x $ nous alors:

• Correction d'un $ (2 ^ n, d, varepsilon) $ - Expander $ g $ et identifiez ses sommets avec $ {0,1 } ^ n $
• Sélectionnez un sommet $ r $ de $ g $ uniformément au hasard
• Calculez l'ensemble $ y_1, y_2, ldots, y_t $ de sommets à distance au plus $ delta $ de $ r $ en $ g $
• Dites "non" si et seulement si $ a (x, r), a (x, y_1), ldots, a (x, y_t) $ sont tous "non"

Ce que je dois montrer, c'est que pour $ delta = o ( log n) $, la probabilité d'un faux négatif est au plus $ n ^ {- c} $.

En tant que note latérale, cela suffit en fait pour atteindre l'objectif original. Le résultat de Gabber et Galil est qu'il existe une famille de $ (2 ^ n, 5, (2 - sqrt {3}) / 4) $ - expanque avec la propriété supplémentaire que les voisins de tout sommet peuvent être énumérés en temps polynomial. Cela signifie que $ d $ et $ varepsilon $ peuvent être pris uniformément dans $ n $, et que nous pouvons implémenter BFS à partir de $ R $ en temps polynomial par sommet. Puisque $ t le d ^ { delta + 1} $, le nouvel algorithme exécute $ a $ un certain nombre de fois polynomial dans $ n $ pour $ delta = o ( log n) $ et $ n $ est polynomial en la taille d'entrée. Étant donné que $ g $ est déterministe et ne dépend pas de $ a $, il n'y a également clairement pas de nouvel aléatoire.

---

Voici comment j'ai abordé le problème jusqu'à présent.

Soit $ g $. Depuis $ | v | = 2 ^ n $, nous avons une identification $ v cong {0,1 } ^ n $. Soit $ r in {0,1 } ^ n $ soit choisi au hasard afin que $ r $ correspond à un point de départ aléatoire dans $ g $. Définir une balle $ b (v, delta) = {u in v: d (u, v) leq delta } $ où $ d (u, v) $ est la longueur du plus court $ uv $ -chemin. Nous ne sommes intéressés que par le nombre de mauvaises boules, à savoir les balles telles que tous les $ u in b (v, delta) $ entraînent de faux négatifs, c'est-à-dire que notre algorithme $ mathsf {rp} $ devrait accepter mais rejeter néanmoins. Si nous pouvons lier au-dessus du nombre de mauvaises boules de 2 $ ^ n / n ^ c $ pour une constante $ c $, alors nous avons fait car une erreur se produit si et seulement si le sommet choisi $ y_i $ est tel que $ b ( y_i, delta) $ est mauvais.

J'ai essayé de délimiter le nombre de sommets dans une mauvaise balle en utilisant la propriété d'expansion de $ g $, mais je ne sais pas comment cela pourrait aider à considérer les balles ne sont certainement pas disjointes. Nous savons également qu'au plus 1/2 $ des sommets se traduiront par un faux négatif.

Toute aide serait grandement appréciée.