Примеры «несвязанной» математики, играющей фундаментальную роль в TCS?

74

Пожалуйста, перечислите примеры, где теорема из математики, которая обычно не считалась применимой в информатике, была впервые использована для доказательства результата в информатике. Лучшими примерами являются те, где связь не была очевидной, но как только она была обнаружена, это, безусловно, «правильный путь» сделать это.

Это противоположное направление вопроса Приложения ТКС к классической математике?

Например, см. «Теорема Грина и изоляция в плоских графах» , где теорема об изоляции (которая уже была известна с помощью технического доказательства) повторно доказана с использованием теоремы Грина из многомерного исчисления.

Какие еще примеры есть?

Derrick Stolee
источник
Сообщество вики.
Дэйв Кларк
Сообщество вики теперь на месте.
Деррик Стоули
Удивительно, сколько примеров о топологии и геометрии. Мы просто более удивлены этими двумя темами?
Суреш Венкат
7
После того, как приведено достаточное количество примеров области X, становится ли эта область X "не связанной"?
Андрас Саламон

Ответы:

38

Морис Херлихи, Майкл Сакс, Нир Шавит и Фотиос Захароглу получили премию Годеля в 2004 году за использование алгебраической топологии при изучении некоторых задач распределенных вычислений.

Уоррен Шуди
источник
1
Это отличный пример!
Райан Уильямс
25

У меня есть пример из работы, которую я в соавторстве с Noga Alon и Muli Safra несколько лет назад:

Нога использовал теоремы о неподвижной точке алгебраической топологии для доказательства «теоремы о расщеплении ожерелья»: если у вас есть ожерелье с бусинками t-типов, и вы хотите разделить его части между b людьми, чтобы каждый получил одинаковое количество бусинок от каждого типа ( Предположим, что b делит t), вы всегда можете сделать это, разрезая ожерелье не более (b-1) t местах.

Мы использовали эту теорему для построения комбинаторного объекта, который мы использовали для доказательства твердости аппроксимации Set-Cover.

Еще немного информации здесь: http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html

Дана Мошковиц
источник
25

Оглядываясь назад, это может быть очевидным, но я всегда любил применение Стилом, Яо и Бен-Ор теоремы Олейника-Петровского / Милнора / Тома (ограничивающей числа Бетти для вещественных полуалгебраических множеств) для доказательства меньшего оценки в алгебраическом дереве решений и алгебраическом дереве вычислений.

Jeffε
источник
1
Результаты «в ретроспективе, это очевидно» - лучший вид приложений. Задним числом является 20/20.
Деррик Стоули
25

Один из моих любимых результатов - использование топологических аргументов в доказательстве Ловаша гипотезы Кнезера и использование топологических ( и теоретико-групповых ) методов в атаке Кан-Сакса-Стертеванта на сильную гипотезу Аандера-Розенберга-Карпа о уклончивости ,

Суреш Венкат
источник
+1. Использование топологических аргументов в доказательстве комбинаторных высказываний действительно эпично. Заинтересованные читатели могут найти больше информации здесь: en.wikipedia.org/wiki/Topological_combinatorics
Робин Котари
1
@ Робин: Или как насчет геометрических аргументов? Основная теорема классической статьи Байера-Диакониса о перетасовке «ласточкиного хвоста» была открыта, когда мы думали о перетасовке как о сохраняющем объем преобразовании (карта пекаря: double и fold (mod 1) вдоль каждой оси) 52-куба. К сожалению, они удалили большинство следов геометрической интуиции из окончательной статьи, заменив ее дискретной комбинаторикой.
Per Vognsen
@Per Vognsen: я не знаком с этой работой, так что спасибо за указатель. Я посмотрю на это.
Робин Котари
2
Возможно, вы захотите добавить «топологические и теоретико-групповые методы» для Кан-Сакса-Стертеванта. В конце концов, они решительно используют групповые действия на симплициальных комплексах.
Джошуа Грохов
2
Мне было интересно, стоит ли "разбудить" эту тему через год, чтобы указать на ссылку ... но тогда это отличная тема, так почему бы и нет. Результат Ловаша и другие результаты, а также введение в «алгебраическую топологию комбинаториалистов» можно найти в монографии Матоусека
Сашо Николов
22

Теория представлений конечных групп используется в подходе Кона-Клейнберга-Сегеди-Уманса к умножению матриц . Они показывают, что если существуют семейства сплетений абелевых с симметричными группами, удовлетворяющие определенным условиям, то существуют алгоритмы матричного умножения квадратичной сложности.

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

Joshua Grochow
источник
21

Таких примеров много. Когда я впервые изучил теорию сложности, я обнаружил удивление, что основные теоремы о корнях многочленов (таких как лемма Шварца-Циппеля-ДеМилло-Липтона) имели какое-либо отношение к вопросу о том, могут ли интерактивные доказательства моделировать пространство многочленов ( ). Конечно, эти свойства полиномов уже использовались в предыдущей работе, и в настоящее время использование «полиномиализирующих» вычислений стало довольно стандартным в теории сложности.IP=PSPACE

Райан Уильямс
источник
7
Мне также нравится полиномиальный трюк для нахождения идеальных совпадений в двудольных графах путем случайной выборки детерминанта (спасибо, Lovász).
Деррик Стоули
21

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

Я думаю, что одно из самых крутых применений инструментов из этой области исходит из этой статьи Бейгеля, Рейнгольда и Спилмана, где они показали, что класс сложности PP замкнут при пересечении, используя тот факт, что функция знака может быть аппроксимирована малым рациональная функция

Нисан, Сегеди и Патури показали нижние оценки для аппроксимации симметрических функций полиномами низкой степени. Этот метод часто используется для доказательства нижних границ сложности квантового запроса. См., Например, лекционные заметки Скотта Ааронсона .

Srikanth
источник
20

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

Суреш Венкат
источник
7
Также доказательство Ноама Нисана лемме о твердом ядре Рассела Импальяццо (в оригинальной статье Рассела)
Дана Мошковиц
17

Теоремы о неподвижной точке повсюду ...

Но довольно удивительным примером появления геометрии из ниоткуда является результат эффективного сравнения. Здесь, учитывая частичный порядок, определенный для набора из элементов, рассмотрим множество перестановок объектов, которые совместимы с данным частичным порядком. Вопрос состоит в том, чтобы выбрать наиболее эффективное сравнение, чтобы сделать следующее; то есть, какое сравнение уменьшило бы число перестановок, совместимых с новым частичным порядком (конечно, есть два возможных частичных порядка, в зависимости от результата этого единственного сравнения). Известно, что всегда есть сравнение, которое сокращает число перестановок на постоянный коэффициент (таким образом, вы можете отсортировать вO ( войдите n ! )nO(logn!)сравнения) Доказательство этого факта проходит через геометрию многомерных многогранников. В частности, в доказательстве используется неравенство Брунна-Минковского. Хорошая презентация этого - в книге Матоусека «Лекции по дискретной геометрии» (раздел 12.3). Оригинальное доказательство - Кан и Линиал, отсюда .

Sariel Har-Peled
источник
15

Существует множество областей применения теории информации в теоретической информатике: например, при доказательстве нижних границ для локально декодируемых кодов (см. Кац и Тревизан), в доказательстве Раза о теореме параллельного повторения, в сложности коммуникации (см., Например, поток работы по сжатию коммуникации, например, относительно недавняя работа Барака, Бравермана, Чена и Рао, и ссылки там), и еще много работы.

Дана Мошковиц
источник
Но действительно ли эти виды использования "не связаны"? По крайней мере, с наивной точки зрения, мне кажется, что теория информации является одной из первых областей, которая приходит на ум, когда кто-то впервые слышит определение, скажем, локально декодируемых кодов.
Арнаб
Я согласен, что теория информации связана, например, с кодами, а коды связаны с TCS. Параллельное повторение, возможно, является более сильным примером: почему вы думаете об использовании его для усиления устойчивости для РСР?
Дана Мошковиц
Да, я полностью согласен с тем, что параллельное повторение является удивительным примером.
Арнаб
14

Алон и Наор использовали неравенство Гротендика, чтобы доказать алгоритм аппроксимации для задачи максимального разреза . Я думаю, что есть последующие работы на эту тему, но я не эксперт.

Интересно, что эта же теорема использовалась Кливом, Хойером, Тонером и Уотроусом для анализа квантовых игр XOR, а Линиал и Шрайбман использовали ее для сложности квантовой коммуникации. Насколько мне известно, связь между неравенством Гротендика и фундаментом квантовой физики была обнаружена Цирельсоном в 85 году, но два упомянутых мною результата конкретно касаются информатики.

Марк
источник
Хм, это не точно. Алон и Наор аппроксимировали норму среза матрицы - это связано с максимальным срезом, но не одинаково.
Сашо Николов
13

Хорошим примером является теорема Баррингтона:

Если булева функция вычисляется по схеме глубины , то вычисляется по программе ветвления шириной 5 и длиной .д ф 4 дfdf4d

В доказательстве используется группа (поскольку она имеет два элемента, сопряженных друг с другом и их коммутатором), но она может быть обобщена для работы с любой неразрешимой группой.S5

Диего де Эстрада
источник
12

Бесстыдная заглушка: использование изотропной гипотезы (и выпуклой геометрии в целом) при разработке примерно оптимальных дифференциально-частных механизмов для линейных запросов в моей работе с Морицем Хардтом .

Чтобы частично ответить на вопрос Суреша выше, я думаю, что оригинальный вопрос немного сложен из-за того, что «его обычно не считают применимым в информатике». Некоторые из этих методов, которые могут казаться изначально «не связанными», со временем становятся «нормальными». Таким образом, наиболее успешные из этих методов (например, анализ Фурье в Кан-Калаи-Линиале, метрические вложения в Линиале-Лондоне-Рабиновиче) больше не являются правильными ответами.

Кунал
источник
Возможно, я перефразирую вопрос, чтобы решить это.
Деррик Стоули
12

Аддитивная комбинаторика / теория чисел часто использовалась в литературе экстракторов. Я думаю, что первые случаи происходят из того, что мы замечаем, что графы Пэли могут быть использованы в качестве хороших экстракторов, и некоторые открытые вопросы в теории аддитивных чисел означают лучшие. Самое раннее упоминание, которое я знаю, - это Цукерман 1990 (см. Его диссертацию ), но в последние несколько лет это была активная область, интересная между TCS и аддитивной комбинаторикой. (Одним из основных моментов является доказательство Двиром гипотезы Кекея о конечном поле, но это, конечно, вклад TCS в математику, а не наоборот.) A-priori непонятно, почему такие математические вопросы касаются сумм и произведений наборов, было бы важно для CS.

Боаз Барак
источник
6
другим хорошим примером в этом ключе является недавнее использование гипотезы Хейлса-Джевитта о плотности для доказательства нелинейной нижней границы на эпсилон-сети для пространства диапазона измерения VC 2.
Суреш Венкат
11

Sleator, Tarjan и Thurston доказали существование бесконечного семейства пар двоичных деревьев поиска с nвершинами и расстоянием вращения, 2n-6используя гиперболическую геометрию.

zotachidil
источник
7

Аддитивная комбинаторика, используемая для построения явной матрицы RIP с строками:o(k2)

Жан Бургейн, Стивен Дж. Дилворт, Кевин Форд, Сергей Конягин, Денка Куцарова: Преодоление барьера для явных матриц RIP. STOC 2011: 637-644.k2

Линейная алгебра, используемая для разбора графов:

Джошуа Д. Батсон, Даниэль А. Спилман, Нихил Шривастава: Дважды рамануджан спарсификаторы. STOC 2009: 255-262.

Джелани Нельсон
источник
6

Это может или не может считаться, но недавно теории Zermelo-Fraenkel с атомами (ZFA) и Fraenkel-Mostowski (FM) были применены для изучения абстрактного синтаксиса с привязкой имен. ZFA был представлен в начале 20-го века как инструмент для доказательства независимости CH, а затем о нем забыли, но он был вновь обнаружен в конце 1990-х годов двумя учеными-компьютерщиками - Габби и Питтсом - изучающими что-то совершенно не связанное.

См. Этот обзорный документ, например.

Доминик Маллиган
источник
4

Кан и Ким применяют энтропию графа для сортировки по частичной информации (http://portal.acm.org/citation.cfm?id=129731). Они дали первый алгоритм полиномиального времени, который выполняет теоретически оптимальное (с точностью до констант) количество сравнений. Работа представляет собой небольшую учебную поездку по математике с использованием некоторых классических комбинаторных аргументов, а также выпуклой геометрии, энтропии графов и выпуклого программирования. Существует более новый более простой алгоритм, но мы все еще знаем, как его анализировать без энтропии графа.

Сашо Николов
источник
3

Теория чисел использовалась для разработки RSA и других криптографических схем с открытым ключом.

Антонио Валерио Мицели-Бароне
источник
0

Открытие умножения Карацубы было удивительным.

user3493
источник
2
Гаусс не согласится.
Джеффс