Amplificazione della correttezza degli algoritmi $ mathsf {rp} $ usando i grafici espansori

Question

Un grafico $ g = (v, e) $ è chiamato $ (n, d, varepsilon) $-espansore Se il grafico ha $ n $ vertici, massimo grado $ d $ e soddisfa quanto segue Proprietà di espansione:

• Per ogni sottoinsieme $ w sottoinsieme v $ tale che $ | w | leq n/2 $, $ | w coppa n (w) | ge (1+ varepsilon) | w | $ $

dove $ n (w) $ è il quartiere di $ w $ in $ g $. La proprietà di espansione significa, in modo informale, che il quartiere di $ w $ è "grande" quando $ w $ è "piccolo". Che esistono espansori possono essere mostrati con il metodo probabilistico (vedi, ad esempio questo Scritto da Ellis).

Sto cercando di dimostrare che gli espansori possono essere usati per amplificare la probabilità di successo degli algoritmi Monte Carlo unilaterale. In particolare, dato un algoritmo di tempo polinomiale $ a $ per un problema in Rp che utilizza $ n $ bit casuali e dà falsi negativi con probabilità al massimo $ 1/2 $ che vogliamo dimostrare che esiste un algoritmo di tempo polinomiale che utilizza bit casuali $ n $ e dà falsi negativi con probabilità al massimo $ n^{-c } $ per una costante fissa $ c $.

Ecco il metodo che mi è stato chiesto di analizzare. Consideriamo $ a $ come una funzione $ a (x, r) $ dove $ x $ è l'input e $ r $ è una stringa che rappresenta i bit casuali. Sull'input $ x $ noi allora:

• Correggi a $ (2^n, d, Varepsilon) $-espander $ g $ e identifica i suoi vertici con $ {0,1 }^n $
• Seleziona un vertice $ r $ di $ g $ uniformemente a caso
• Calcola il set $ y_1, y_2, ldots, y_t $ di vertici a distanza al massimo $ delta $ da $ r $ in $ g $
• Di '"no" se e solo se $ a (x, r), a (x, y_1), ldots, a (x, y_t) $ sono tutti "no"

Quello che devo mostrare è che per $ delta = o ( log n) $ la probabilità di un falso negativo è al massimo $ n^{-c} $.

Come nota a margine, questo è in realtà sufficiente per raggiungere l'obiettivo originale. Un risultato di Gabber e Galil è che esiste una famiglia di $ (2^n, 5, (2 - sqrt {3})/4) $ - espansori con la proprietà aggiuntiva che i vicini di qualsiasi vertice possano essere elencati in tempo polinomiale. Ciò significa che $ D $ e $ Varepsilon $ può essere preso in modo uniforme in $ n $ e che possiamo implementare BFS da $ r $ in tempo polinomiale per vertice considerato. Poiché $ t le d^{ delta + 1} $, il nuovo algoritmo esegue $ a $ un numero di volte polinomiale in $ n $ per $ Delta = o ( log n) $ e $ n $ è polinomiale in la dimensione dell'input. Poiché $ g $ è deterministico e non dipende da $ a $, non c'è chiaramente nessuna nuova casualità.

---

Ecco come ho affrontato il problema finora.

Lascia che $ g $ venga dato. Dato $ | V | = 2^n $, abbiamo un'identificazione $ v cong {0,1 }^n $. Lascia che $ r in {0,1 }^n $ sia scelto a caso in modo che $ r $ corrisponda a un punto di partenza casuale in $ g $. Definisci una palla $ b (v, delta) = {u in v: d (u, v) leq Delta } $ dove $ d (u, v) $ è la lunghezza del più corto $ uv $ -sentiero. Siamo interessati solo al numero di palle cattive, vale a dire le palle in modo tale che tutte le $ u in b (v, delta) $ risultano in falsi negativi, cioè il nostro algoritmo $ mathsf {rp} $ dovrebbe accettare ma rifiutare comunque. Se possiamo limitare al di sopra del numero di sfere cattive di $ 2^n/n^c $ per qualche costante $ c $, allora abbiamo finito poiché si verifica un errore se e solo se il vertice scelto $ y_i $ è tale che $ b ( y_i, Delta) $ è cattivo.

Ho provato a delimitare il numero di vertici in una palla cattiva usando la proprietà di espansione di $ g $, ma non sono sicuro di come ciò possa aiutare a considerare le palle non siano certamente disgiunte. Sappiamo anche che al massimo $ 1/2 $ dei vertici si tradurranno in un falso negativo.

Qualsiasi aiuto sarebbe molto apprezzato.