Изменения

Покажем, что у нового алгоритма вероятность ошибки не превосходит <tex>1/d</tex>. В самом деле, обозначим <tex>B = B(x)</tex> множество таких вершин <tex>w</tex> из правой доли графа, которые соответствуют неверному ответу старого алгоритма на входе <tex>x</tex>; аналогично, обозначим <tex>S = S(x)</tex> множество таких вершин v из левой доли графа, которые для которых новый алгоритм даёт неверный ответ на входе <tex>x</tex>. Очевидно, <tex>S</tex> состоит из вершин, все соседи которых лежат в B. Предположим, что <tex>S</tex> содержит не менее <tex>n/(1000d)</tex> вершин. Выберем среди них ровно <tex>n/(1000d)</tex> вершин и назовём это множество <tex>S'</tex>. По свойству экспандера, имеем

Это противоречит тому, что все соседи <tex>S'</tex> лежат в <tex>B</tex>. В данном случае нам нужна явная в более сильном (чем в первом примере) смысле конструкция экспандера. Размер графа экспоненциално растёт с увеличенем <tex>k</tex>, и нам необходим алгоритм, который по заданному номеру вершины <tex>v</tex> (из левой доли графа) за время <tex>poly(k)</tex> находит список номеров всех соседей этой вершины (в правой доле графа).