Теория информации используется для доказательства аккуратных комбинаторных утверждений?

54

Какие ваши любимые примеры, когда теория информации используется, чтобы доказать аккуратное комбинаторное утверждение простым способом?

Некоторые примеры, которые я могу придумать, связаны с нижними границами для локально декодируемых кодов, например, в этой статье: предположим, что для двоичных строк длины он содержит то, что для каждого i , для k_i различного пары { j_1, j_2 }, e_i = x_ {j_1} \ oplus x_ {j_2}. Тогда m по крайней мере экспоненциально по n, где показатель степени линейно зависит от среднего отношения k_i / m . н яx1,...,xmnij 1 , j 2 e i = x j 1x j 2 . к я / мkij1,j2

ei=xj1xj2.
ki/m

Другой (связанный) пример - это некоторые изопериметрические неравенства в булевом кубе (не стесняйтесь уточнять это в своих ответах).

У вас есть более приятные примеры? Желательно, кратко и легко объяснить.

Дана Мошковиц
источник
может кто-нибудь дать ссылку на «Другой (связанный) пример - это некоторые изопериметрические неравенства на булевом кубе»?
vzn

Ответы:

40

Доказательство Мозером конструктивной локальной леммы Ловаша . Он в основном показывает, что в условиях локальной леммы второй по простоте алгоритм для SAT вы можете себе представить. (Первым простым может быть просто попытаться выполнить случайное назначение, пока оно не сработает. Второе простейшее - это выбрать случайное назначение, найти неудовлетворенное предложение, удовлетворить его, а затем посмотреть, какие другие предложения вы нарушили, повторить и повторить до выполнения.) Доказательство того, что это выполняется за полиномиальное время, является, пожалуй, самым элегантным использованием теории информации (или сложности Колмогорова, как бы вы ни хотели это назвать в этом случае), которую я когда-либо видел.

Джошуа Грохов
источник
1
Прекрасное колмогоровское доказательство сложности Мозера объясняется здесь: blog.computationalcomplexity.org/2009/06/… , но я должен признать, что я искал больше для примера типа энтропии / взаимной информации / расчета ...
Дана Мошковиц
Есть несколько довольно интересных приложений сложности Колмогорова, приведенных в качестве ответов на этот вопрос: cstheory.stackexchange.com/questions/286
arnab
Терри Тао также обсудил аргумент Мозера в своем блоге: terrytao.wordpress.com/2009/08/05/…
Энтони Леверье
5
На самом деле, в его второй статье (с Тардосом) вам больше не нужно прибегать к рекурсии. Вы просто ищете неудовлетворенное предложение, выбираете случайное назначение для его переменных и выполняете итерацию . Вот и все. По какой-то причине более простой алгоритм (с таким же анализом) не застрял.
Юваль Фильмус
@DanaMoshkovitz: Я не знаю, почему мне не пришло в голову ответить раньше на ваш комментарий: сложность и энтропия Колмогорова во многом эквивалентны. См., Например, Хаммер-Ромащенко-Шен-Вершагин: dx.doi.org/10.1006/jcss.1999.1677 . Например, на основе [HRSV] доказательство леммы Ширера в ответе Арнаба может быть доказано по существу тем же доказательством с использованием колмогоровской сложности вместо энтропии. Разница только в точке зрения: K - это длина описания, H - это ... Иногда одно легче / более естественно, чем другое. pilogpi
Джошуа Грохов
33

Мой любимый пример этого типа - основанное на энтропии доказательство леммы Ширера. (Я узнал об этом и некоторых других очень красивых доказательствах из « Энтропии и счета Джайкумара Радхакришнана» .)

Утверждение. Предположим, у вас есть точек в которые имеют различных проекций на плоскости , различных проекций на плоскости и различных проекций на плоскости . Тогда .R 3 n x y z n y x z n z x y n 2n x n y n znR3nxyznyxznzxyn2nxnynz

Доказательство. Пусть - точка, случайно выбранная из точек. Пусть , , обозначают его проекции на плоскости , и соответственно. n p x p y p z y z x z x yp=(x,y,z)npxpypzyzxzxy

С одной стороны, , , и , по основным свойствам энтропии.H [ p x ] log n x H [ p y ] log n y H [ p z ] log n zH[p]=lognH[px]lognxH[py]lognyH[pz]lognz

С другой стороны, имеем а также Добавление трех последних уравнений дает нам: , где мы использовали тот факт, что обусловливание уменьшает энтропию (обычно для любых случайных величин ).H [ p x ] = H [ y ] + H [ z | y ] H [ p y ] = H [ x ] + H [ z | х ] Н [p z ] = H [ x ] + H [ y | х ] Н [ р х ] + Н | y ] 2 H [ x ]

H[p]=H[x]+H[y|x]+H[z|x,y]
H[px]=H[y]+H[z|y]
H[py]=H[x]+H[z|x]
H[pz]=H[x]+H[y|x]
2 H [ x ] + H [ y ] + H [ y | x ] + H [ z | x ] + H [ zH[px]+H[py]+H[pz]= 2H[x]+H[y]+ H[y|x]+ H[z|x] +H[z|y] 2H[x]+2H[y|x]+2H[z|x,y]= 2H[p]H[a]H[a|b]a,b

Таким образом, мы имеем или .n 2n x n y n z2lognlognx+logny+lognzn2nxnynz

Арнаб
источник
6
Эхуд Фридгут: «Гиперграфы, энтропия и неравенства». Он показывает, как энтропийная перспектива, в частности обобщенная лемма Ширера, может легко восстановить многие стандартные неравенства, а также некоторые нестандартные, сложные на вид. Я думаю, что это дает осветительную перспективу. Ссылка: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf
Энди Друкер
26

Энтропийное доказательство теоремы Брегмана Радхакришнана о том , что число совершенных соответствий в двудольном графе не больше . В доказательстве используются две очень умные идеи. Вот набросок доказательства:( L R , E ) v L ( d ( v ) ! ) 1 / d ( v )p(LR,E)vL(d(v)!)1/d(v)

  • Выберите идеальное соответствие равномерно. Энтропия этой переменной .H ( M ) = log pMH(M)=logp
  • Для , пусть вершина в , что согласуется с в .X v R v MvLXvRvM
  • Переменная имеет ту же информацию, что и , поэтому .X=(Xv:vL)MH(M)=H(X)
  • Умная идея 1: случайно (и равномерно) выбирая порядок на , Радхакришнан предоставляет «правило случайной цепочки», в котором говорится, что .LH(X)=vLH(Xv|Xu:u<v,)
  • Из информации в условиях ( ) мы можем определить(примерно: количество вариантов для соответствия ).Xu:u<v,Nv=|N(v)Xu:u<v|v
  • Поскольку определяется из этой информации, условная энтропия не изменяется в равенстве .NvH(Xv|Xu:u<v,)=H(Xv|Xu:u<v,,Nv)
  • Умная идея 2: «забыв» информацию , мы можем только увеличить энтропию: .Xu:u<v,H(Xv|Xu:u<v,,Nv)H(Xv|Nv)
  • Сумасшедший факт: переменная равномерно распределена на множестве .Nv1,,d(v)
  • Теперь, чтобы вычислить энтропию , мы суммируем по всем значениям :H(Xv|Nv)NvH(Xv|Nv)=i=1d(v)1d(v)H(Xv|Nv=i)1d(v)i=1d(v)logi=log((d(v)!)1/d(v)).
  • Результат следует, объединяя все неравенства вместе и принимая показатели.

Обобщением этого неравенства является теорема Канна-Ловаша: число совершенных совпадений в любом графе не более . Энтропийное доказательство этого результата было доказано Катлером и Рэдклиффом .GvV(G)(d(v)!)1/2d(v)

Деррик Стоули
источник
1
Отличный пример! Небольшой момент: когда вы оцениваете , вы, вероятно, можете только сказать, что ограничен сверху . H(XvNv)H(XvNv=i)logi
Srikanth
Вы абсолютно правы, и я отредактировал ответ, чтобы использовать неравенство.
Деррик Столи
20

Прекрасные примеры содержатся в двух статьях Пиппенгера «Теоретико-информационный метод в комбинаторной теории». J. Comb. Теория, Сер. A 23 (1): 99-104 (1977) и энтропия и перечисление булевых функций. IEEE Труды по теории информации 45 (6): 2096-2100 (1999). На самом деле, несколько работ Пиппенгера содержат симпатичные доказательства комбинаторных фактов посредством энтропии / взаимной информации. Кроме того, две книги: Jukna, Extremal Combinatorics с приложениями в области компьютерных наук и Aigner, Combinatorial Search содержат несколько хороших примеров. Мне также нравятся две статьи Madiman et al. Информационно-теоретические неравенства в аддитивной комбинаторике и Теренс Тао, оценки сумм энтропии (их можно найти с помощью Google Scholar). Надеюсь, это поможет.

Ugo
источник
Выглядит как отличный список для чтения!
Дана Мошковиц
17

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

Позвольте мне попытаться объяснить на очень высоком уровне эту теоретико-информационную перспективу.

Предположим, у вас есть двудольный граф с двумя наборами вершин и и множеством ребер E подмножество . Плотность ребер равна, Мы говорим, что является -регулярным, если для всех и плотность подграфа, индуцированного и равна,GV1V2V1×V2Gρ=|E|/|V1||V2|GϵU1V1U2V2U1U2ρ±ϵ|U1||U2|/|V1||V2|

Теперь рассмотрим выбор вершины из и вершины из , независимо и равномерно наугад. Если мало, а велико, мы можем интерпретировать -регулярность как выражение, что обусловливание в и в не сильно влияет на вероятность того, что образует края в . Другими словами, даже после того, как нам дали информацию, что находится в иx1V1x2V2ϵU1,U2ϵGx1U1x2U2(x1,x2)Gx1U1x2 находится в , мы не получили много информации о том является ли ребром или нет.U2(x1,x2)

Лемма регулярности Семереди (неформально) гарантирует, что для любого графа можно найти разбиение и разбиение на подмножества постоянной плотности, так что для большинства таких пар подмножеств индуцированный подграф на является -регулярным. Делая вышеприведенную интерпретацию, учитывая любые две высокоэнтропийные переменные и и любое событие , можно найти переменные с низкой энтропией и - «low- энтропия ", потому что подмножества иV1V2U1V1,U2V2U1×U2ϵx1x2E(x1,x2)U1(x1)U2(x2)U1U2 имеют постоянную плотность - так что приблизительно не зависит от и , или что взаимная информация между переменными очень мала. Тао фактически формулирует гораздо более сильную версию леммы регулярности, используя эту настройку. Например, он не требует, чтобы и были независимыми переменными (хотя, насколько я знаю, применения этого обобщения еще не было). Ex1|U1x2|U2x1x2

оборота арнаб
источник
15

В основном этому вопросу посвящен целый курс:

https://catalyst.uw.edu/workspace/anuprao/15415/86751

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

Moritz
источник
3
хороший указатель: выглядит как отличный класс.
Суреш Венкат
1
Насколько я могу судить, это предложение состоит из половины курса, с примечаниями, содержащими некоторые примеры, которые дают хорошие ответы на мой вопрос, и с половиной семинара, охватывающего такие примеры, как нижние границы коммуникации, экстракторы, параллельное повторение и т. Д., Которые требуют гораздо большего, чем просто теория информации (здесь нет заметок, просто ссылки на оригинальные статьи).
Дана Мошковиц
7

Предположим, у нас есть точек в и мы хотим уменьшить размерность. Если мы хотим, чтобы попарные расстояния изменялись не более чем на , то мы можем уменьшить наше измерение с до . Это лемма Джонсона-Линденштраусса . В течение десятилетия самой известной нижней границей для измерения был Алон, , поэтому имел место разрыв в размере . Недавно Джейрам и Вудрафф закрылисьn2d1±ϵdO(logn/ϵ2)Ω(logn/(ϵ2log(1/ϵ)))log(1/ϵ)этот разрыв путем улучшения нижней границы Алона. Их доказательство едва опирается на геометрическую структуру. Они доказывают, что если бы лучшая граница была возможна, это нарушило бы одну нижнюю границу сложности коммуникации. И эта оценка доказана с помощью информационно-теоретических средств.

ilyaraz
источник
4
Другой пример в метрических вложениях: Регев недавно показал очень краткое доказательство лучших границ для вложения в , используя аргументы энтропии. 1d
Арнаб
Кажется очень естественным и приятным, что эти чисто геометрические результаты были доказаны людьми TCS!
Ильяраз
6

Рассмотрим следующую довольно фундаментальную проблему в мире структур данных. У вас есть вселенная размером . Вы хотите сохранить элемент в качестве структуры статических данных, так что , когда пользователь хочет знать , если для некоторых ли , только укусил зонды в структуру данных необходимы где некоторая фиксированная константа. Цель состоит в том, чтобы минимизировать пространственную сложность структуры данных (с точки зрения количества хранимых битов).mu[m]x[m]x=utt

Можно построить такую ​​структуру данных размером . Идея проста. Разделите битов, необходимых для описания на блоков. Для каждого и для каждого возможного бистринга длины сохраните в структуре данных, равен ли -й блок из этой цепочке битов.O(m1/t)logmuti[t](logm)/tiu

Теперь для нижней границы. Пусть - элемент, случайно выбранный случайным образом из . Ясно, что . Если являются битами, измеренными в структуре данных (возможно, адаптивно) в этой последовательности, то: , где - размер структуры данных. Это дает: .[ m ] H [ X ] = log m X 1 , , X t t H [ X ] = H [ X 1 ] + H [ X 2 | X 1 ] + + H [ X t | X 1 , , X t - 1 ] t log s sX[m]H[X]=logmX1,,XttH[X]=H[X1]+H[X2|X1]++H[Xt|X1,,Xt1]tlogsssm1/t

Точные границы неизвестны, если мы хотим сохранить два элемента и . Смотрите здесь для лучших результатов в этом направлении.t>1

оборота арнаб
источник
5

Отличным примером является статья " Сортировка и энтропия " Кан и Ким. Энтропия метод используется , чтобы найти алгоритм , который дал известный посетом и unknon линейное расширение , найти линейное расширение по запросов , где является множество линейных расширений .P O ( log | X | ) XPPO(log|X|)XP

Гил Калай
источник
3

Анализ средних случаев алгоритмов с использованием колмогоровской сложности по Jiang, Li, Vitanyi.

«Анализ сложности алгоритмов в среднем случае - очень практичная, но очень сложная проблема в информатике. В последние несколько лет мы показали, что колмогоровская сложность является важным инструментом для анализа средней сложности алгоритмов. Мы разработали метод несжимаемости [7]. В этой статье мы используем несколько простых примеров, чтобы дополнительно продемонстрировать силу и простоту такого метода. Мы доказываем границы среднего количества стеков (очередей), необходимых для сортировки последовательных или параллельных Queueusort или Stacksort. '

См. Также, например, колмогоровскую сложность и задачу о треугольнике типа Хейльбронна .

Нил Янг
источник
3

Эквивалентность выборки и поиска по Скотту Ааронсону. Здесь он показывает эквивалентность проблемы выборки и поиска в теории сложности в отношении обоснованности расширенного тезиса Черча-Тьюринга. Стандартная теория информации, алгоритмическая теория информации и колмогоровская сложность используются фундаментально.

Он подчеркивает:
« Подчеркнем, что мы не используем колмогоровскую сложность как просто техническое удобство или как условное обозначение для счетного аргумента. Скорее, колмогоровская сложность кажется существенной даже для определения проблемы поиска ».

DurgaDatta
источник
0

Это просто, а также приблизительное: сколько комбинаций из 10 6 вещей из 10 9 , допускающих дублирование? Правильная формула

N = (10 6 + 10 9 )! / (10 6 ! 10 9 !) ~ = 2 11409189.141937481

Но представьте, что вы даете инструкции пройтись по ряду миллиардов ведер, бросая по пути миллион шариков в ведра. Там будет ~ 10 9 "шаг к следующему ведру" инструкции и 10 6 "капля мрамора" инструкции. Общая информация

log 2 (N) ~ = -10 6 log 2 (10 6 / (10 6 + 10 9 )) - 10 9 log 2 (10 9 / (10 6 + 10 9 )) ~ = 11409200.432742426

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

(а + б)! / а! б! ~ = (a + b) (a + b) / a a b b

что похоже на приближение Стирлинга, отмена и пропущение чего-либо.

FutureNerd
источник
2
Это может быть более читабельным, если вы делаете общую оценку, а не конкретные цифры. Я думаю, что вы говорите об энтропийном приближении объема шара Хэмминга.
Сашо Николов