В математике и теоретической информатики , анализ функций булевыми является изучение вещественных функций на или же (такие функции иногда называют псевдобулевыми функциями ) со спектральной точки зрения. [1] Изучаемые функции часто, но не всегда, являются булевозначными, что делает их булевыми функциями . Эта область нашла множество применений в комбинаторике , теории социального выбора , случайных графах и теоретической информатике, особенно в области жесткости аппроксимации , тестирования свойств и обучения PAC .
Основные понятия
В основном мы будем рассматривать функции, определенные в домене . Иногда удобнее работать с доменомвместо. Если определяется на , то соответствующая функция, определенная на является
Точно так же для нас логическая функция - это -значная функция, хотя часто удобнее рассматривать вместо этого -значные функции.
Разложение Фурье
Каждая функция с действительным знаком имеет уникальное разложение как полилинейный многочлен:
Это преобразование Адамара функции, являющееся преобразованием Фурье в группе . Коэффициентыизвестны как коэффициенты Фурье , и вся сумма известна как разложения Фурье от. Функцииизвестны как характеры Фурье , и они образуют ортонормированный базис для пространства всех функций над, относительно внутреннего продукта .
Коэффициенты Фурье можно рассчитать с помощью внутреннего произведения:
В частности, это показывает, что , где математическое ожидание берется относительно равномерного распределения по. Личность Парсеваля утверждает, что
Если мы пропустим , то получаем дисперсию :
Степень Фурье и уровни Фурье
Степень функции это максимум такой, что для некоторого набора размера . Другими словами, степень - его степень как полилинейного многочлена.
Разложение Фурье удобно разложить по уровням : коэффициент Фурье находится на уровне .
степень часть является
Получается из обнулением всех коэффициентов Фурье не на уровне .
Аналогично определяем .
Влияние
В влияние функции можно определить двумя эквивалентными способами:
Если является логическим, тогда вероятность того, что перевернуть Координата 'переворачивает значение функции:
Если тогда не зависит от координата.
Общее влияние на это сумма всех его влияний:
Общее влияние логической функции - это также средняя чувствительность функции. Чувствительность булевой функции в данной точке - это количество координат так что если мы перевернем координата, значение функции изменится. Среднее значение этой величины и есть полное влияние.
Суммарное влияние также может быть определена с использованием дискретного лапласиана в графе Хэмминга , соответственно нормализованы:.
Обобщенная форма влияния - это -стабильное влияние, определяемое:
Соответствующие суммарные влияния равны
Можно доказать, что функция имеет самое большее «постоянно» много «стабильно влиятельных» координат:
Шумоустойчивость
Дано , мы говорим, что два случайных вектора находятся -коррелирован, если маргинальные распределения единообразны, и . Конкретно, мы можем сгенерировать пару-коррелированные случайные величины по первому выбору равномерно наугад, а затем выбирая в соответствии с одним из следующих двух эквивалентных правил, применяемых независимо к каждой координате:
Обозначим это распределение через .
Помехоустойчивость функции в можно определить двумя эквивалентными способами:
Для , То чувствительность к шуму из в является
Если является логическим, то это вероятность того, что значение изменяется, если мы перевернем каждую координату с вероятностью , независимо.
Оператор шума
Оператор шума оператор, принимающий функцию и возвращая другую функцию дано
Когда оператор шума также может быть определен с помощью цепочки Маркова с непрерывным временем, в которой каждый бит переворачивается независимо со скоростью 1. Оператор соответствует запуску этой цепи Маркова для шаги, начиная с , и взяв среднее значение в конечном состоянии. Эта цепь Маркова порождается лапласианом графа Хэмминга, и это связывает полное влияние с оператором шума.
Шумоустойчивость можно определить с помощью оператора шума: .
Гиперсонтрастность
Для , то -норма функции определяется
Мы также определяем
Теорема о сверхсжимаемости утверждает, что для любого а также ,
Hypercontractivity тесно связано с логарифмическим Соболева неравенств из функционального анализа . [2]
Аналогичный результат для известен как обратная гиперсокращаемость . [3]
p -Смещенный анализ
Во многих ситуациях входные данные функции не распределяются равномерно по , но вместо этого имеет склонность к или же . В этих ситуациях принято рассматривать функции над областью. Для, мера со смещением p дан кем-то
Эта мера может быть сгенерирована путем выбора каждой координаты независимо как 1 с вероятностью и 0 с вероятностью .
Классические характеры Фурье больше не ортогональны по этой мере. Вместо этого мы используем следующие символы:
Р -biased разложение Фурье расширение как линейная комбинация символов со смещением p :
Мы можем расширить определения влияния и оператора шума на настройку со смещением p , используя их спектральные определения.
Влияние
В влияние дается
Общее влияние - это сумма отдельных влияний:
Оператор шума
Пара -коррелированные случайные величины можно получить, выбрав самостоятельно и , где дан кем-то
Тогда оператор шума дается выражением
Используя это, мы можем определить устойчивость к шуму и чувствительность к шуму, как и раньше.
Формула Руссо – Маргулиса
Формула Руссо – Маргулиса (также называемая формулой Маргулиса – Руссо [1] ) утверждает, что для монотонных булевых функций,
И влияние, и вероятности взяты относительно , а в правой части - средняя чувствительность . Если мы подумаем о как свойство, то формула утверждает, что как варьируется, производная от вероятности того, что происходит в равна средней чувствительности при .
Формула Руссо – Маргулиса является ключевой для доказательства точных пороговых теорем, таких как теоремы Фридгута .
Гауссово пространство
Один из самых глубоких результатов в этой области, принцип инвариантности , связывает распределение функций на булевом кубеих распределению на гауссовском пространстве , которое является пространством наделен стандартом -мерная гауссовская мера .
Многие из основных концепций анализа Фурье на булевом кубе имеют аналоги в гауссовском пространстве:
- Аналогом разложения Фурье в гауссовском пространстве является разложение Эрмита, которое представляет собой разложение до бесконечной суммы (сходящееся в ) многомерных многочленов Эрмита .
- Аналогом общего влияния или средней чувствительности для индикаторной функции набора является площадь поверхности по Гауссу, которая является содержанием Минковского границы набора.
- Аналогом оператора шума является оператор Орнштейна – Уленбека (связанный с преобразованием Мелера ), задаваемый формулой, или альтернативно , где пара -коррелированные стандартные гауссианы.
- Гиперсжимаемость сохраняется (с соответствующими параметрами) и в гауссовском пространстве.
Гауссово пространство более симметрично, чем булев куб (например, он инвариантен к вращению), и поддерживает непрерывные аргументы, которые может быть труднее передать при дискретной настройке булевого куба. Принцип инвариантности связывает эти две настройки и позволяет вывести результаты на булевом кубе из результатов на гауссовском пространстве.
Основные результаты
Теорема Фридгута – Калаи – Наора.
Если имеет степень не выше 1, то либо константа, либо равна координате, либо равна отрицанию координаты. В частности,это диктатура : функция, зависящая не более чем от одной координаты.
Теорема Фридгута – Калаи – Наора [4], также известная как теорема ФКН , утверждает, что если почти имеет степень 1, тогда это близко к диктатуре. Количественно, если а также , тогда является - близко к диктатуре, то есть для некоторой булевой диктатуры , или, что эквивалентно, для некоторой булевой диктатуры .
Аналогично, булева функция степени не выше зависит не более чем от координаты, что делает его хунтой (функция, зависящая от постоянного числа координат), гдеявляется абсолютной константой, равной не менее 1,5 и не более 4,41, как показал Велленс. Теорема Киндлера – Сафры [5] обобщает теорему Фридгута – Калаи – Наора на этот случай. В нем говорится, что если удовлетворяет тогда является -близко к булевой функции степени не выше .
Теорема Кана – Калаи – Линиала
Неравенство Пуанкаре для булевого куба (вытекающее из приведенных выше формул) утверждает, что для функции ,
Это означает, что .
Теорема Кана – Калаи – Линиала [6], также известная как теорема ККЛ , утверждает, что если является логическим, тогда .
Ограничение, данное теоремой Кана – Калаи – Линиала, является точным и достигается с помощью функции Tribes Бен-Ор и Линиаль: [7]
Теорема Кана – Калаи – Линиала была одним из первых результатов в этой области и ввела сверхсжимаемость в контекст булевых функций.
Теорема Фридгута о хунте
Если является -junta (функция, зависящая не более чем от координаты) тогда согласно неравенству Пуанкаре.
Теорема Фридгута [8] обратна этому результату. В нем говорится, что для любого, функция является -Близко к булевой хунте в зависимости от координаты.
В сочетании с леммой Руссо – Маргулиса из теоремы Фридгута о хунте следует, что для каждого , каждая монотонная функция близка к хунте по для некоторых .
Принцип инвариантности
Принцип инвариантности [9] обобщает теорему Берри – Эссеена на нелинейные функции.
Теорема Берри – Эссеена утверждает (среди прочего), что если и нет слишком велико по сравнению с остальными, то распределение над близка к нормальному распределению с тем же средним значением и дисперсией.
Принцип инвариантности (в частном случае) неформально утверждает, что если является полилинейным многочленом ограниченной степени над и все влияния малы, то распределение по единой мере над близко к его распределению в гауссовом пространстве.
Более формально, пусть - одномерная липшицева функция , пусть, позволять , и разреши . Предположим, что. потом
Выбрав подходящий , это означает, что распределения при обоих измерениях близки по расстоянию CDF , которое определяется как.
Принцип инвариантности был ключевым элементом в первоначальном доказательстве большинства является стабильной теоремой .
Некоторые приложения
Проверка линейности
Булева функция является линейным , если оно удовлетворяет, где . Нетрудно показать, что булевы линейные функции - это в точности символы.
При тестировании свойств мы хотим проверить, является ли данная функция линейной. Естественно попробовать следующий тест: выберите равномерно наугад и проверьте, что . Еслилинейно, то он всегда проходит проверку. Блюм, Люби и Рубинфельд [10] показали, что если тест проходит с вероятностью тогда является -близко к фурье-характеру. Их доказательство было комбинаторным.
Bellare et al. [11] предоставили чрезвычайно простое фурье-аналитическое доказательство, которое также показывает, что если тест с вероятностью успешен, тогда соотносится с характером Фурье. Их доказательство основано на следующей формуле вероятности успеха теста:
Теорема Эрроу
Теорема о невозможности Эрроу гласит, что для трех и более кандидатов единственное правило единогласного голосования, для которого всегда есть победитель Кондорсе, - это диктатура.
Обычное доказательство теоремы Эрроу комбинаторно. Калаи [12] дал альтернативное доказательство этого результата в случае трех кандидатов, используя анализ Фурье. Если является правилом, которое назначает победителя среди двух кандидатов с учетом их относительного порядка в голосовании, тогда вероятность того, что есть победитель Кондорсе при равномерно случайном голосовании, равна , откуда легко следует теорема.
Из теоремы FKN следует, что если это правило, для которого почти всегда есть победитель по Кондорсе, то близок к диктатуре.
Острые пороги
Классический результат теории случайных графов утверждает, что вероятность того, что случайный граф связан, стремится к если . Это пример резкого порога : ширина «порогового окна», которое, асимптотически меньше самого порога, который примерно равен . Напротив, вероятность того, что график содержит треугольник, стремящийся к когда . Здесь и пороговое окно, и сам порог, так что это грубый порог .
Теорема Фридгута о точном пороге [13] , грубо говоря, утверждает, что свойство монотонного графа (свойство графа - это свойство, которое не зависит от имен вершин) имеет резкий порог, если только оно не коррелирует с появлением небольших подграфов . Эта теорема широко применяется для анализа случайных графов и перколяции .
В связи с этим, из теоремы ККЛ следует, что ширина порогового окна всегда не превышает. [14]
Большинство стабильно
Позволять обозначим функцию большинства на координаты. Формула Шеппарда дает асимптотическую помехоустойчивость большинства:
Это связано с вероятностью того, что если мы выберем равномерно случайным образом и формируют переворачивая каждый бит с вероятностью , то большинство остается прежним:
- .
Есть булевы функции с большей помехоустойчивостью. Например, диктатура имеет шумоустойчивость .
Теорема «Большинство - это самая стабильная» неформально утверждает, что единственные функции, обладающие большей помехоустойчивостью, чем большинство, имеют влиятельные координаты. Формально для каждого Существует так что если имеет нулевое ожидание и , тогда .
Первое доказательство этой теоремы использовало принцип инвариантности в сочетании с изопериметрической теоремой Борелла в гауссовском пространстве; с тех пор были придуманы более прямые доказательства. [ необходима цитата ]
«Большинство стабильно» означает, что алгоритм приближения Гоэманса – Вильямсона для MAX-CUT является оптимальным, исходя из гипотезы об уникальных играх . Этот вывод, сделанный Хотом и др. [15], послужил толчком к доказательству теоремы.
Рекомендации
- ^ а б О'Доннелл, Райан (2014). Анализ булевых функций . Издательство Кембриджского университета. ISBN 978-1-107-03832-5.
- ^ P. Diaconis ; Л. Салофф-Кост (август 1996 г.). «Логарифмические неравенства Соболева для конечных цепей Маркова». Анналы прикладной теории вероятностей . 6 (3): 695–750. DOI : 10.1214 / AOAP / 1034968224 . ISSN 1050-5164 . Руководство по ремонту 1410112 . Zbl 0867.60043 . Викиданные Q62111462 .
- ^ Моссель, Эльханан; Олешкевич, Кшиштоф; Сен, Арнаб (2013). «Об обратной сверхсокращаемости». GAFA . 23 (3): 1062–1097. arXiv : 1108.1210 . DOI : 10.1007 / s00039-013-0229-4 . S2CID 15933352 .
- ^ Фридгут, Эхуд; Калаи, Гил; Наор, Ассаф (2002). «Булевы функции, преобразование Фурье которых сосредоточено на первых двух уровнях». Успехи в прикладной математике . 29 (3): 427–437. DOI : 10.1016 / S0196-8858 (02) 00024-6 .
- ^ Киндлер, Гай (2002). «16». Проверка собственности, PCP и хунты (Диссертация). Тель-Авивский университет.
- ^ Кан, Джефф; Калаи, Гил; Линиал, Нати (1988). «Влияние переменных на булевы функции». Proc. 29-й симпозиум по основам информатики . SFCS'88. Белые равнины: IEEE. С. 68–80. DOI : 10.1109 / SFCS.1988.21923 .
- ^ Бен-Ор, Майкл; Linial, Натан (1985). «Коллективное подбрасывание монет, надежные схемы голосования и минимумы ценностей Банцафа». Proc. 26-й симпозиум по основам информатики . SFCS'85. Портленд, Орегон: IEEE. С. 408–416. DOI : 10.1109 / SFCS.1985.15 .
- ^ Фридгут, Эхуд (1998). «Булевы функции с низкой средней чувствительностью зависят от нескольких координат». Combinatorica . 18 (1): 474–483. CiteSeerX 10.1.1.7.5597 . DOI : 10.1007 / PL00009809 . S2CID 15534278 .
- ^ Моссель, Эльханан; О'Доннелл, Райан; Олешкевич, Кшиштоф (2010). «Шумоустойчивость функций с низкими воздействиями: инвариантность и оптимальность». Анналы математики . 171 (1): 295–341. arXiv : math / 0503503 . DOI : 10.4007 / анналы.2010.171.295 .
- ^ Блюм, Мануэль; Луби, Майкл; Рубинфельд, Ронитт (1993). «Самотестирование / исправление с приложениями к численным задачам». J. Comput. Syst. Sci . 47 (3): 549–595. DOI : 10.1016 / 0022-0000 (93) 90044-W .
- ^ Белларе, Михир; Медник, Дон; Хастад, Йохан; Киви, Маркос; Судан, Мадху (1995). «Проверка линейности характеристики два». Proc. 36-й симпозиум по основам информатики . FOCS'95.
- ^ Калаи, Гил (2002). «Теоретико-Фурье-взгляд на парадокс Кондорсе и теорему Эрроу» (PDF) . Adv. Прил. Математика . 29 (3): 412–426. DOI : 10.1016 / S0196-8858 (02) 00023-4 .
- ^ Фридгут, Эхуд (1999). «Точные пороги свойств графа и проблема k-SAT» . Варенье. Математика. Soc . 12 (4): 1017–1054. DOI : 10.1090 / S0894-0347-99-00305-7 .
- ^ Фридгут, Эхуд; Калаи, Гил (1996). «Каждое свойство монотонного графа имеет резкий порог» . Proc. Являюсь. Математика. Soc . 124 (10): 2993–3002. DOI : 10.1090 / S0002-9939-96-03732-X .
- ^ Хот, Субхаш ; Киндлер, Гай; Моссель, Эльханан; О'Доннелл, Райан (2007), "Оптимальные результаты несовместимости для MAX-CUT и других CSP с двумя переменными?" (PDF) , SIAM Journal on Computing , 37 (1): 319–357, CiteSeerX 10.1.1.130.8886 , DOI : 10.1137 / S0097539705447372