Вопросы о булевых функциях и их анализ
За эти годы я привык видеть много теорем TCS, доказанных с использованием дискретного анализа Фурье. Преобразование Уолша-Фурье (Адамара) полезно практически во всех подполях TCS, включая тестирование свойств, псевдослучайность, сложность связи и квантовые вычисления. Хотя мне стало удобно...
Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Пусть - булева функция, и давайте подумаем о f как о функции от до . На этом языке разложение Фурье функции f является просто разложением функции f по квадратным свободным мономам. (Эти мономов образуют базис для пространства вещественных функций на . Сумма квадратов коэффициентов равна просто так...
Машине PHPHPH предоставляется оракулу доступ к случайной булевой функции f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} и двум спектрам Фурье ggg и hhh . Спектры Фурье функции fff определяются как F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R :...
Недавнее и невероятно приятное доказательство гипотезы о чувствительности основано на явном * построении матрицы An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times 2^n} , определенной рекурсивно следующим образом: A1=(0110)A1=(0110)A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix} и, для, В...
В последние несколько месяцев я начал читать лекции о социальном выборе, теореме стрелы и связанных с ней результатах. Прочитав об исходных результатах, я спросил себя о том, что происходит с предпочтениями частичного порядка, ответ в статье Pini et al. : Агрегирование частично упорядоченных...
Состояние наших знаний об общих арифметических схемах похоже на состояние наших знаний о булевых схемах, то есть у нас нет хороших нижних границ. С другой стороны, мы имеем экспоненциальный размер нижних границ для монотонных булевых цепей . Что мы знаем о монотонных арифметических схемах? У нас...
Есть ли (разумный) способ выбрать равномерно случайную булеву функцию , степень которой как вещественный полином не превосходит ?f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd РЕДАКТИРОВАТЬ: Нисан и Сегеди показали, что функция степени зависит не более чем от координат, поэтому мы можем...
Основное свойство векторных пространств состоит в том, что векторное пространство размерности может характеризоваться линейно независимыми линейными ограничениями, то есть существуют линейно независимых векторов , ортогональных .В⊆ FN2В⊆F2NV \subseteq \mathbb{F}_2^nн - дN-dn-dddddddвес1, … , Шd∈...
Все ли функции, чей вес Фурье сконцентрирован на множествах малого размера (или членах с низкой степенью), вычисляются по схемам
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...
Некоторая работа по чувствительности против чувствительности блоков была направлена на изучение функций с максимально большим промежутком между и , чтобы развить гипотезу, что только полиномиально больше, чем . Как насчет противоположного направления? Что известно о функциях, где...
Мы говорим, что булева функция f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} является юнтой, если имеет не более влияющих переменных.к kkф ffкkk Пусть - -юнта. Обозначим переменные через . Исправить Ясно, что существует такой, что содержит хотя бы из влияющих переменных .f : { 0...
В проблеме, над которой я сейчас работаю, естественно возникает расширение оператора шума, и мне было любопытно, была ли ранее работа. Сначала позвольте мне пересмотреть основной оператор шума для вещественных булевых функций. Для данной функции и , st , , мы определяем как...
Я пытаюсь понять сложность функций, которые можно выразить через пороговые элементы, и это привело меня к . В частности, мне интересно, что в настоящее время известно об обучении в , так как я не эксперт в этой области.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 На данный момент я обнаружил, что: Все из...
Является ли следующая проблема в PTIME или coNP-hard: Даны два булевых выражения и в переменных без отрицания (т. Е. Выражения полностью построены с помощью и ). Решите, есть ли , то есть имеют ли они одинаковое значение для всех назначений переменных.е1е1e_1е2е2e_2Икс1, … ,...
Я представлю свою проблему на примере. Скажем, вы разрабатываете экзамен, который состоит из определенного набора независимых вопросов (которые кандидаты могут получить как правильно, так и неправильно). Вы хотите принять решение о балле, который нужно дать для каждого из вопросов, при этом правило...
SAT решатели дают мощный способ проверить правильность логической формулы с одним квантификатором. Например, чтобы проверить правильность , мы можем использовать SAT-решатель, чтобы определить, выполнимо ли . Чтобы проверить правильность , мы можем использовать SAT-решатель, чтобы определить,...
В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения: Здесь проблема не в конструктивности - все свойства,...