Анализ булевых функций

В математике и информатике теоретической анализ булевых функций — это изучение вещественных функций на $\{0,1\}^{n}$ или $\{-1,1\}^{n}$ (такие функции иногда называют псевдобулевыми функциями ) со спектральной точки зрения. Изучаемые функции часто, но не всегда, имеют булевы значения, что делает их булевыми функциями . Эта область нашла множество применений в комбинаторике , теории социального выбора , случайных графах и теоретической информатике, особенно в трудностях аппроксимации , тестировании свойств и PAC-обучении .

Основные понятия

В основном мы будем рассматривать функции, определенные в области определения $\{-1,1\}^{n}$. Иногда удобнее работать с доменом $\{0,1\}^{n}$ вместо. Если $f$ определяется на $\{-1,1\}^{n}$, то соответствующая функция, определенная на $\{0,1\}^{n}$ является

$f_{01}(x_{1},\ldots ,x_{n})=f((-1)^{x_{1}},\ldots ,(-1)^{x_{n}}).$

Аналогично, для нас булева функция — это $\{-1,1\}$-значная функция, хотя часто удобнее рассматривать $\{0,1\}$вместо этого -значные функции.

Разложение Фурье

Любая вещественная функция $f\colon \{-1,1\}^{n}\to \mathbb {R}$ имеет уникальное разложение в виде полилинейного многочлена:

$f(x)=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}(x),\quad \chi _{S}(x)=\prod _{i\in S}x_{i}.$

(Обратите внимание, что даже если функция имеет значение 0–1, это не сумма по модулю 2, а обычная сумма действительных чисел.)

Это преобразование Адамара функции $f$, что является преобразованием Фурье в группе $\mathbb {Z} _{2}^{n}$. Коэффициенты ${\hat {f}}(S)$ известны как коэффициенты Фурье , а вся сумма известна как Фурье разложение $f$. Функции $\chi _{S}$ известны как характеры Фурье и образуют ортонормированный базис пространства всех функций над $\{-1,1\}^{n}$, относительно внутреннего продукта $\langle f,g\rangle =2^{-n}\sum _{x\in \{-1,1\}^{n}}f(x)g(x)$.

Коэффициенты Фурье можно рассчитать с помощью внутреннего продукта:

${\hat {f}}(S)=\langle f,\chi _{S}\rangle .$

В частности, это показывает, что ${\hat {f}}(\emptyset )=\operatorname {E} [f]$, где ожидаемое значение берется относительно равномерного распределения по $\{-1,1\}^{n}$. Личность Парсеваля гласит, что

$\|f\|^{2}=\operatorname {E} [f^{2}]=\sum _{S}{\hat {f}}(S)^{2}.$

Если мы пропустим $S=\emptyset$, то мы получим дисперсию $f$:

$\operatorname {Var} [f]=\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}.$

Степень Фурье и уровни Фурье

Степень ​ функции $f\colon \{-1,1\}^{n}\to \mathbb {R}$ это максимум $d$ такой, что ${\hat {f}}(S)\neq 0$ для какого-то набора $S$ размера $d$. Другими словами, степень $f$ — его степень как полилинейного полинома.

Разложение Фурье удобно разложить на уровни : коэффициент Фурье ${\hat {f}}(S)$ находится на уровне $|S|$.

Степень ​ $d$ часть $f$ является

$f^{=d}=\sum _{|S|=d}{\hat {f}}(S)\chi _{S}.$

Его получают из $f$ путем обнуления всех коэффициентов Фурье, не находящихся на уровне $d$.

Аналогично определяем $f^{>d},f^{<d},f^{\geq d},f^{\leq d}$.

Влияние

The $i$'-ое влияние функции $f\colon \{-1,1\}^{n}\to \mathbb {R}$ можно определить двумя эквивалентными способами:

${\begin{aligned}&\operatorname {Inf} _{i}[f]=\operatorname {E} \left[\left({\frac {f-f^{\oplus i}}{2}}\right)^{2}\right]=\sum _{S\ni i}{\hat {f}}(S)^{2},\\[5pt]&f^{\oplus i}(x_{1},\ldots ,x_{n})=f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n}).\end{aligned}}$

Если $f$ тогда это логическое значение $\operatorname {Inf} _{i}[f]$ вероятность того, что переворот $i$'-я координата переворачивает значение функции:

$\operatorname {Inf} _{i}[f]=\Pr[f(x)\neq f^{\oplus i}(x)].$

Если $\operatorname {Inf} _{i}[f]=0$ затем $f$ не зависит от $i$'я координата.

влияние Общее ​ $f$ представляет собой сумму всех его влияний:

$\operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.$

Общее влияние булевой функции также является средней чувствительностью функции. Чувствительность функции булевой $f$ в данной точке - это количество координат $i$ так что если мы перевернем $i$'-я координата, значение функции изменяется. Среднее значение этой величины и есть полное влияние.

Общее влияние также можно определить с помощью дискретного лапласиана графа Хэмминга , нормализованного соответствующим образом: $\operatorname {Inf} [f]=\langle f,Lf\rangle$.

Обобщенной формой воздействия является $\rho$-стабильное влияние, определяемое:

$\operatorname {Inf} _{i}^{\,(\rho )}[f]=\operatorname {Stab} _{\rho }[\operatorname {D} _{i}f]=\sum _{S\ni i}\rho ^{|S|-1}{\hat {f}}(S)^{2}.$

Соответствующие суммарные влияния

$\operatorname {I} ^{(\rho )}[f]={\frac {d}{d\rho }}\operatorname {Stab} _{\rho }[f]=\sum _{S}|S|\rho ^{|S|-1}{\hat {f}}(S)^{2}.$

Можно доказать, что функция $f:\{-1,1\}^{n}\to \{-1,1\}$ имеет максимум «постоянно» много«стабильно-влиятельные» координаты: $|\{i\in [n]:\operatorname {Inf} _{i}^{\,(1-\delta )}[f]\geq \epsilon \}|\leq {\frac {1}{\delta \epsilon }}.$

Шумоустойчивость

Данный $-1\leq \rho \leq 1$, мы говорим, что два случайных вектора $x,y\in \{-1,1\}^{n}$ являются $\rho$-коррелированы, если предельные распределения $x,y$ однородны, и $\operatorname {E} [x_{i}y_{i}]=\rho$. Конкретно, мы можем сгенерировать пару $\rho$-коррелированные случайные величины при первом выборе $x,z\in \{-1,1\}^{n}$ равномерно случайным образом, а затем выбирая $y$ согласно одному из следующих двух эквивалентных правил, применяемых независимо к каждой координате:

$y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}\quad {\text{or}}\quad y_{i}={\begin{cases}x_{i}&{\text{w.p. }}{\frac {1+\rho }{2}},\\-x_{i}&{\text{w.p. }}{\frac {1-\rho }{2}}.\end{cases}}$

Обозначим это распределение через $y\sim N_{\rho }(x)$.

Шумоустойчивость ​ функции $f\colon \{-1,1\}^{n}\to \mathbb {R}$ в $\rho$ можно определить двумя эквивалентными способами:

$\operatorname {Stab} _{\rho }[f]=\operatorname {E} _{x;y\sim N_{\rho }(x)}[f(x)f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)^{2}.$

Для $0\leq \delta \leq 1$, чувствительность шумовая $f$ в $\delta$ является

$\operatorname {NS} _{\delta }[f]={\frac {1}{2}}-{\frac {1}{2}}\operatorname {Stab} _{1-2\delta }[f].$

Если $f$ является логическим, то это вероятность того, что значение $f$ изменится, если мы перевернем каждую координату с вероятностью $\delta$, независимо.

Шумовой оператор

Шумовой оператор $T_{\rho }$ это оператор, принимающий функцию $f\colon \{-1,1\}^{n}\to \mathbb {R}$ и возвращаем другую функцию $T_{\rho }f\colon \{-1,1\}^{n}\to \mathbb {R}$ данный

$(T_{\rho }f)(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)]=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\chi _{S}.$

Когда $\rho >0$, оператор шума также может быть определен с использованием цепи Маркова с непрерывным временем , в которой каждый бит инвертируется независимо со скоростью 1. Оператор $T_{\rho }$ соответствует запуску этой цепи Маркова для ${\frac {1}{2}}\log {\frac {1}{\rho }}$ шаги, начиная с $x$и взяв среднее значение $f$ в конечном состоянии. Эта цепь Маркова порождается лапласианом графа Хэмминга, и это связывает общее влияние с оператором шума.

Шумоустойчивость можно определить с помощью оператора шума: $\operatorname {Stab} _{\rho }[f]=\langle f,T_{\rho }f\rangle$.

Гиперконтрактивность

Для $1\leq q<\infty$, $L_{q}$-норма функции $f\colon \{-1,1\}^{n}\to \mathbb {R}$ определяется

$\|f\|_{q}={\sqrt[{q}]{\operatorname {E} [|f|^{q}]}}.$

Мы также определяем $\|f\|_{\infty }=\max _{x\in \{-1,1\}^{n}}|f(x)|.$

Теорема о гиперсжатии утверждает, что для любого $q>2$ и $q'=1/(1-1/q)$,

$\|T_{\rho }f\|_{q}\leq \|f\|_{2}\quad {\text{and}}\quad \|T_{\rho }f\|_{2}\leq \|f\|_{q'}.$

Гиперсжимаемость тесно связана с логарифмическими неравенствами Соболева функционального анализа .

Аналогичный результат для $q<2$ известна как обратная гиперконтрактивность .

р- предвзятый анализ

Во многих ситуациях входные данные функции распределены неравномерно. $\{-1,1\}^{n}$, но вместо этого имеет уклон в сторону $-1$ или $1$. В таких ситуациях принято рассматривать функции над областью определения. $\{0,1\}^{n}$. Для $0<p<1$, p -смещенная мера $\mu _{p}$ дается

$\mu _{p}(x)=p^{\sum _{i}x_{i}}(1-p)^{\sum _{i}(1-x_{i})}.$

Эту меру можно получить, выбрав каждую координату независимо равной 1 с вероятностью $p$ и 0 с вероятностью $1-p$.

Классические характеры Фурье уже не ортогональны относительно этой меры. Вместо этого мы используем следующие символы:

$\omega _{S}(x)=\left({\sqrt {\frac {p}{1-p}}}\right)^{|\{i\in S:x_{i}=0\}|}\left(-{\sqrt {\frac {1-p}{p}}}\right)^{|\{i\in S:x_{i}=1\}|}.$

- смещенное p разложение Фурье $f$ это расширение $f$ как линейная комбинация p -смещенных символов:

$f=\sum _{S\subseteq [n]}{\hat {f}}(S)\omega _{S}.$

Мы можем расширить определения влияния и оператора шума на случай p -смещения, используя их спектральные определения.

Влияние

The $i$влияние России определяется

$\operatorname {Inf} _{i}[f]=\sum _{S\ni i}{\hat {f}}(S)^{2}=p(1-p)\operatorname {E} [(f-f^{\oplus i})^{2}].$

Общее влияние представляет собой сумму отдельных влияний:

$\operatorname {Inf} [f]=\sum _{i=1}^{n}\operatorname {Inf} _{i}[f]=\sum _{S}|S|{\hat {f}}(S)^{2}.$

Шумовой оператор

Пара $\rho$-коррелированные случайные величины можно получить, выбрав $x,z\sim \mu _{p}$ независимо и $y\sim N_{\rho }(x)$, где $N_{\rho }$ дается

$y_{i}={\begin{cases}x_{i}&{\text{w.p. }}\rho ,\\z_{i}&{\text{w.p. }}1-\rho .\end{cases}}$

Тогда оператор шума имеет вид

$(T_{\rho }f)(x)=\sum _{S\subseteq [n]}\rho ^{|S|}{\hat {f}}(S)\omega _{S}(x)=\operatorname {E} _{y\sim N_{\rho }(x)}[f(y)].$

Используя это, мы можем определить шумоустойчивость и чувствительность к шуму, как и раньше.

Формула Руссо-Маргулиса

Формула Руссо-Маргулиса (также называемая формулой Маргулиса-Руссо) ) утверждает, что для монотонных булевых функций $f\colon \{0,1\}^{n}\to \{0,1\}$,

${\frac {d}{dp}}\operatorname {E} _{x\sim \mu _{p}}[f(x)]={\frac {\operatorname {Inf} [f]}{p(1-p)}}=\sum _{i=1}^{n}\Pr[f\neq f^{\oplus i}].$

И влияние, и вероятности берутся относительно $\mu _{p}$, а в правой части — средняя чувствительность $f$. Если мы думаем о $f$ как свойство, то формула гласит, что поскольку $p$ варьируется, производная вероятности того, что $f$ происходит в $p$ равна средней чувствительности при $p$.

Формула Руссо-Маргулиса является ключом к доказательству точных пороговых теорем, таких как теорема Фридгута .

Гауссово пространство

Один из самых глубоких результатов в этой области, принцип инвариантности , связывает распределение функций на булевом кубе. $\{-1,1\}^{n}$ их распределению в гауссовском пространстве , которое представляет собой пространство $\mathbb {R} ^{n}$ наделенный стандартом $n$-мерная гауссова мера .

Многие из основных концепций анализа Фурье в булевом кубе имеют аналоги в гауссовском пространстве:

• Аналогом разложения Фурье в гауссовском пространстве является разложение Эрмита, которое представляет собой разложение до бесконечной суммы (сходящееся в $L^{2}$) многомерных полиномов Эрмита .
• Аналогом общего влияния или средней чувствительности для индикаторной функции набора является площадь гауссовой поверхности, которая представляет собой содержание Минковского на границе набора.
• Аналогом оператора шума является оператор Орнштейна – Уленбека (связанный с преобразованием Мелера ), определяемый формулой $(U_{\rho }f)(x)=\operatorname {E} _{z\sim N(0,1)}[f(\rho x+{\sqrt {1-\rho ^{2}}}z)]$или, альтернативно, $(U_{\rho }f)(x)=\operatorname {E} [f(y)]$, где $x,y$ это пара $\rho$-коррелированные стандартные гауссианы.
• Гиперсжатие имеет место (с соответствующими параметрами) и в гауссовском пространстве.

Гауссово пространство более симметрично, чем булев куб (например, оно инвариантно вращению), и поддерживает непрерывные аргументы, которые может быть сложнее пройти в дискретной настройке булева куба. Принцип инвариантности связывает эти две настройки и позволяет выводить результаты в булевом кубе из результатов в гауссовском пространстве.

Основные результаты

Теорема Фридгута – Калаи – Наора

Если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ имеет степень не более 1, то $f$ либо константа, равна координате, либо равна отрицанию координаты. В частности, $f$ это диктатура : функция, зависящая не более чем от одной координаты.

Теорема Фридгута–Калаи–Наора, также известная как теорема ФКН , утверждает, что если $f$ почти имеет степень 1, то это близко к диктатуре. Количественно, если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ и $\|f^{>1}\|^{2}<\varepsilon$, затем $f$ является $O(\varepsilon )$-близко к диктатуре, то есть, $\|f-g\|^{2}=O(\varepsilon )$ для некоторой булевой диктатуры $g$или, что то же самое, $\Pr[f\neq g]=O(\varepsilon )$ для некоторой булевой диктатуры $g$.

Аналогично, булева функция степени не более $d$ зависит максимум от $C_{W}2^{d}$ координаты, что делает его хунтой (функция, зависящая от постоянного числа координат), где $C_{W}$ является абсолютной константой, равной не менее 1,5 и не более 4,41, как показал Велленс. Теорема Киндлера–Сафры обобщает теорему Фридгута – Калаи – Наора на этот случай. В нем говорится, что если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ удовлетворяет $\|f^{>d}\|^{2}<\varepsilon$ затем $f$ является $O(\varepsilon )$-близко к булевой функции степени не более $d$.

Теорема Кана–Калаи–Линиала

Неравенство Пуанкаре для булева куба (следующее из приведенных выше формул) утверждает, что для функции $f\colon \{-1,1\}^{n}\to \mathbb {R}$,

$\operatorname {Var} [f]\leq \operatorname {Inf} [f]\leq \deg f\cdot \operatorname {Var} [f].$

Это означает, что $\max _{i}\operatorname {Inf} _{i}[f]\geq {\frac {\operatorname {Var} [f]}{n}}$.

Теорема Кана–Калаи–Линиала, также известная как теорема ККЛ , утверждает, что если $f$ тогда это логическое значение $\max _{i}\operatorname {Inf} _{i}[f]=\Omega \left({\frac {\log n}{n}}\right)$.

Граница, данная теоремой Кана–Калаи–Линиала, является точной и достигается с помощью функции Трайба Бен-Ора и Линиала:

$(x_{1,1}\land \cdots \land x_{1,w})\lor \cdots \lor (x_{2^{w},1}\land \cdots \land x_{2^{w},w}).$

Теорема Кана-Калаи-Линиала была одним из первых результатов в этой области и ввела гиперсжимаемость в контекст булевых функций.

Теорема Фридгута о хунте

Если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ это $M$-хунта (функция, зависящая не более чем от $M$ координаты) тогда $\operatorname {Inf} [f]\leq M$ согласно неравенству Пуанкаре.

Теорема Фридгута является обратным этому результату. В нем говорится, что для любого $\varepsilon >0$, функция $f$ является $\varepsilon$-близко к булевой хунте в зависимости от $\exp(\operatorname {Inf} [f]/\varepsilon )$ координаты.

В сочетании с леммой Руссо-Маргулиса теорема Фридгута о хунте означает, что для любого $p$, каждая монотонная функция близка к хунте по отношению к $\mu _{q}$ для некоторых $q\approx p$.

Принцип инвариантности

Принцип инвариантности обобщает теорему Берри–Эссеена на нелинейные функции.

Теорема Берри–Эссеена утверждает (среди прочего), что если $f=\sum _{i=1}^{n}c_{i}x_{i}$ и нет $c_{i}$ слишком велико по сравнению с остальными, то распределение $f$ над $\{-1,1\}^{n}$ близко к нормальному распределению с тем же средним значением и дисперсией.

Принцип инвариантности (в частном случае) неформально гласит, что если $f$ является полилинейным полиномом ограниченной степени над $x_{1},\ldots ,x_{n}$ и все влияния $f$ малы, то распределение $f$ под единой мерой в течение $\{-1,1\}^{n}$ близко к его распределению в гауссовском пространстве.

Более формально, пусть $\psi$ — одномерная липшицева функция , пусть $f=\sum _{S\subseteq [n]}{\hat {f}}(S)\chi _{S}$, позволять $k=\deg f$, и пусть $\varepsilon =\max _{i}\sum _{S\ni i}{\hat {f}}(S)^{2}$. Предположим, что $\sum _{S\neq \emptyset }{\hat {f}}(S)^{2}\leq 1$. Затем

$\left|\operatorname {E} _{x\sim \{-1,1\}^{n}}[\psi (f(x))]-\operatorname {E} _{g\sim N(0,I)}[\psi (f(g))]\right|=O(k9^{k}\varepsilon ).$

Выбрав подходящее $\psi$, это означает, что распределения $f$ по обеим мерам близки по расстоянию CDF , которое определяется выражением $\sup _{t}|\Pr[f(x)<t]-\Pr[f(g)<t]|$.

Принцип инвариантности был ключевым ингредиентом в первоначальном доказательстве «Большинство стабильнее» теоремы .

Некоторые приложения

Проверка линейности

Булева функция $f\colon \{-1,1\}^{n}\to \{-1,1\}$ является линейным, если оно удовлетворяет $f(xy)=f(x)f(y)$, где $xy=(x_{1}y_{1},\ldots ,x_{n}y_{n})$. Нетрудно показать, что булевы линейные функции — это в точности символы $\chi _{S}$.

При тестировании свойств мы хотим проверить, является ли данная функция линейной. Естественно провести следующий тест: выберите $x,y\in \{-1,1\}^{n}$ равномерно случайным образом и проверьте, что $f(xy)=f(x)f(y)$. Если $f$ линейна, то она всегда проходит тест. Блюм, Люби и Рубинфельд показал, что если тест проходит с вероятностью $1-\varepsilon$ затем $f$ является $O(\varepsilon )$-близко к фурье-характеру. Их доказательство было комбинаторным.

Белларе и др. дал чрезвычайно простое фурье-аналитическое доказательство, которое также показывает, что если тест успешен с вероятностью $1/2+\varepsilon$, затем $f$ коррелирует с характером Фурье. Их доказательство основано на следующей формуле вероятности успеха теста:

${\frac {1}{2}}+{\frac {1}{2}}\sum _{S\subseteq [n]}{\hat {f}}(S)^{3}.$

Теорема Эрроу

Теорема невозможности Эрроу утверждает, что для трех и более кандидатов единственным правилом единогласного голосования, при котором всегда есть победитель Кондорсе, является диктатура.

Обычное доказательство теоремы Эрроу является комбинаторным. Калай дал альтернативное доказательство этого результата в случае трех кандидатов с использованием анализа Фурье. Если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ - это правило, которое определяет победителя среди двух кандидатов с учетом их относительного порядка голосов, тогда вероятность того, что победит Кондорсе при равномерно случайном голосовании, равна ${\frac {3}{4}}-{\frac {3}{4}}\operatorname {Stab} _{-1/3}[f]$, откуда легко следует теорема.

Теорема ФКН означает, что если $f$ это правило, по которому почти всегда есть победитель Кондорсе, тогда $f$ близок к диктатуре.

Острые пороги

Классический результат теории случайных графов гласит, что вероятность того, что $G(n,p)$ случайный граф связен, имеет тенденцию к $e^{-e^{-c}}$ если $p\sim {\frac {\log n+c}{n}}$. Это пример резкого порога : ширина «порогового окна», $O(1/n)$, асимптотически меньше самого порога, который примерно равен ${\frac {\log n}{n}}$. Напротив, вероятность того, что $G(n,p)$ граф содержит треугольник, стремится к $e^{-c^{3}/6}$ когда $p\sim {\frac {c}{n}}$. Здесь и пороговое окно, и сам порог $\Theta (1/n)$, и так это грубый порог .

Точная пороговая теорема Фридгута Грубо говоря, утверждается, что свойство монотонного графа (свойство графа — это свойство, не зависящее от имен вершин) имеет резкий порог, если только оно не коррелирует с появлением небольших подграфов. Эта теорема широко применялась для анализа случайных графов и перколяции .

Попутно из теоремы ККЛ следует, что ширина порогового окна всегда не превышает $O(1/\log n)$.

Большинство наиболее стабильно

Позволять $\operatorname {Maj} _{n}\colon \{-1,1\}^{n}\to \{-1,1\}$ обозначим мажоритарную функцию на $n$ координаты. Формула Шеппарда дает асимптотическую шумовую устойчивость большинства:

$\operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]\longrightarrow 1-{\frac {2}{\pi }}\arccos \rho .$

Это связано с вероятностью того, что если мы выберем $x\in \{-1,1\}^{n}$ равномерно случайным образом и образуют $y\in \{-1,1\}^{n}$ переворачивая каждый бит $x$ с вероятностью ${\frac {1-\rho }{2}}$, то большинство останется прежним:

$\operatorname {Stab} _{\rho }[\operatorname {Maj} _{n}]=2\Pr[\operatorname {Maj} _{n}(x)=\operatorname {Maj} _{n}(y)]-1$.

Существуют логические функции с большей шумоустойчивостью. Например, диктатура $x_{i}$ имеет шумоустойчивость $\rho$.

Теорема «Большинство стабильнейших» гласит, неформально, что единственные функции, устойчивость к шуму большая, чем у большинства, имеют влиятельные координаты. Формально для каждого $\varepsilon >0$ существует $\tau >0$ такое, что если $f\colon \{-1,1\}^{n}\to \{-1,1\}$ имеет нулевое ожидание и $\max _{i}\operatorname {Inf} _{i}[f]\leq \tau$, затем $\operatorname {Stab} _{\rho }[f]\leq 1-{\frac {2}{\pi }}\arccos \rho +\varepsilon$.

Первое доказательство этой теоремы использовало принцип инвариантности в сочетании с изопериметрической теоремой Борелла в гауссовском пространстве; с тех пор были изобретены более прямые доказательства.

Большинство стабильнее означает, что алгоритм аппроксимации Гоеманса-Вильямсона для MAX-CUT является оптимальным, если предположить гипотезу об уникальных играх . Этот вывод, по мнению Хота и др., послужило толчком к доказательству теоремы.