Чисто теоретико-графическое объяснение редукции от уникального покрытия этикетки до Max-Cut

9

Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей собственной неясности относительно этой эквивалентности я изо всех сил стараюсь следовать этому ходу мыслей.

Из этих изложений также ясно, что можно описать сокращение исключительно в виде графиков, но по стечению обстоятельств или предпочтениям никто не решит сделать это таким образом. Например, в этих лекционных заметках О'Доннелла он намекает на то, что тест длинного кода соответствует естественному определению ребер в строящемся графе, но поскольку не указано, что правило, по-видимому, зависит от выбора разреза определить тестируемую булеву функцию, и это меня несколько смутило.

Поэтому я прошу кого-то объяснить теоретическое сокращение «просто». Я думаю, что это поможет мне понять эквивалентность между двумя точками зрения.

Джереми Кун
источник

Ответы:

10

Позвольте мне посмотреть, смогу ли я уточнить это на высоком уровне. Предположим, что экземпляр UG является двудольным графомG=(VW,E)Биографии {πe}eE, где πe:ΣΣ, а также |Σ|=m, Вы хотите построить новый графикH так что если экземпляр UG 1δ удовлетворительно, то H имеет большой разрез, и если экземпляр UG даже не δнеудовлетворительно, то H имеет только очень маленькие порезы.

График H содержит, для каждой вершины в Wоблако 2m точки, каждая помечена некоторыми x{1,1}Σ, Предполагается, что вы сможете интерпретировать длинную кодовую метку метокW в разрезе H, Напомним, что для кодирования некоторыхσΣ с длинным кодом вы используете булеву функцию f:{1,1}Σ{1,1}; в частности это функция диктатораf(x)=xσ, Давайте сделаем разрезST(т. е. двунаправленное разбиение вершин) из кодирования длинного кода следующим образом. ЕслиwW имеет метку, закодированную булевой функцией fиди к облаку вершин в H соответствует wи положить в S все вершины в облаке, которые помечены некоторыми x для которого f(x)=1, Все остальные идут вT, Вы можете сделать это задом наперед, чтобы назначить булевы функции всемwW основанный на разрезе H,

Для того чтобы сокращение работало, вы должны быть в состоянии сказать только, глядя на значение сокращенияST близки ли логические функции, соответствующие вырезанию, к кодированию длинного кода некоторого назначения меток W что удовлетворяет многим ограничениям UG G, Таким образом, вопрос в том, какую информацию мы получаем от стоимости разрезаST, Рассмотрим любые две вершиныa с этикеткой x в облаке, соответствующем w а также b с этикеткой y в облаке, соответствующем w (в сокращении мы только смотрим на w, wв разных облаках). Мы сказали, что разрез может быть использован для получения булевых функцийfw а также fw, Теперь, если есть преимущество(a,b) в H, тогда (a,b) режется тогда и только тогда, когда fw(x)fw(y), Следовательно, использование только значения среза для определения того, являются ли булевы функции, которые он вызывает, «хорошими», равнозначно тому, чтобы иметь тест с заданными булевыми функциями.{fw}wW, только спрашивает, какая часть некоторого указанного списка пар ((w,x),(w,y)) у нас есть fw(x)fw(y),

Другими словами, всякий раз, когда Райан говорит в примечаниях "проверить, если fw(x)fw(y)"что он на самом деле означает" в H, добавить ребро между вершиной в облаке w помечены x и вершина в облаке w помечены yТ.е. для каждого vVкаждые два его соседа w,wи каждый x,y{1,1}n, включить ребро между вершиной в облаке w помечены xπv,w и вершина в облаке w помечены yπv,wи назначьте вес ребра ((1ρ)/2)d((1+ρ)/2)nd где d это расстояние Хэмминга между x а также y, Таким образом, значение среза, деленное на общий вес ребра, точно равно вероятности успеха теста.

Сашо Николов
источник
Это отличный ответ, который мне нужно изучить более подробно. У меня есть небольшой дополнительный вопрос: должен ли я подозревать, что сокращение, которое я ожидаю, будет детерминированным, все еще имеет этот случайный компонент генерацииμ?
Джереми Кун
Извините, это моделируется путем добавления ребер для всех векторов в поддержку xμи присвоение граничных весов, пропорциональных вероятностям. Исправлена.
Сашо Николов