Teoria da informação usada para provar declarações combinatórias puras?

54

Quais são os seus exemplos favoritos em que a teoria da informação é usada para provar uma declaração combinatória pura de uma maneira simples?

Alguns exemplos em que posso pensar estão relacionados a limites mais baixos para códigos decodificáveis ​​localmente, por exemplo, neste artigo: suponha que, para um monte de cadeias binárias de comprimento isso seja válido para todo , para diferente pares { },Então m é pelo menos exponencial em n, onde o expoente depende linearmente da razão média de . n i k i j 1 , j 2 e i = x j 1x j 2 . k i / mx1,...,xmnikij1,j2

ei=xj1xj2.
ki/m

Outro exemplo (relacionado) são algumas desigualdades isoperimétricas no cubo booleano (fique à vontade para elaborar isso em suas respostas).

Você tem exemplos mais legais? De preferência, curto e fácil de explicar.

Dana Moshkovitz
fonte
alguém pode dar uma ref em "Outro exemplo (relacionado) são algumas desigualdades isoperimétricas no cubo booleano"?
vzn

Respostas:

40

A prova de Moser do construtor local Lemma de Lovasz . Ele basicamente mostra que, nas condições do lema local, o segundo algoritmo mais simples para SAT que você pode imaginar funciona. (O primeiro mais simples pode ser apenas tentar uma tarefa aleatória até que alguém funcione. O segundo mais simples é escolher uma tarefa aleatória, encontrar uma cláusula insatisfeita, satisfazê-la e depois ver quais outras cláusulas você quebrou, repetiu e repetiu até terminar.) A prova de que isso ocorre no tempo polinomial é talvez o uso mais elegante da teoria da informação (ou da complexidade de Kolmogorov, como você quiser chamar nesse caso) que eu já vi.

Joshua Grochow
fonte
11
A bela prova de Moser da complexidade de Kolmogorov é explicada aqui: blog.computationalcomplexity.org/2009/06/… , mas devo admitir que estava procurando mais um exemplo de tipo de entropia / informação mútua / cálculo ...
Dana Moshkovitz
Há algumas aplicações muito interessantes de Complexidade de Kolmogorov dadas como respostas a esta pergunta: cstheory.stackexchange.com/questions/286
Arnab
Terry Tao também discutiu o argumento de Moser em seu blog: terrytao.wordpress.com/2009/08/05/…
Anthony Leverrier
5
Na verdade, em seu segundo artigo (com Tardos), você não precisa mais recorrer à recursão. Você apenas procura uma cláusula não satisfeita, escolhe uma atribuição aleatória para suas variáveis ​​e itera . É isso aí. Por alguma razão, o algoritmo mais simples (com a mesma análise) não parou.
Yuval Filmus
@DanaMoshkovitz: Não sei por que isso não me ocorreu mais cedo em resposta ao seu comentário: complexidade e entropia de Kolmogorov são, em muitos aspectos, essencialmente equivalentes. Ver, por exemplo, Hammer-Romaschenko-Shen-Vershchagin: dx.doi.org/10.1006/jcss.1999.1677 . Por exemplo, com base em [HRSV], a prova do Lema de Shearer na resposta de arnab pode ser provada com essencialmente a mesma prova usando a complexidade de Kolmogorov no lugar da entropia. A diferença é apenas o ponto de vista: K é sobre o comprimento da descrição, H é sobre ... Às vezes, um é mais fácil / mais natural que o outro. pilogpi
Joshua Grochow 12/02
33

Meu exemplo favorito desse tipo é a prova baseada em entropia do Lema de Shearer's. (Aprendi sobre essa prova e várias outras muito bonitas da Entropy and Counting de Jaikumar Radhakrishnan .)

Reivindicação: Suponha que você tenha pontos em que tenham projeções distintas no plano , projeções distintas no plano e projeções distintas no plano . Então, .R 3 n x y z n y x z n z x y n 2n x n y n znR3nxyznyxznzxyn2nxnynz

Prova: Seja um ponto uniformemente escolhido aleatoriamente dentre os pontos. Deixe , , denotam suas projecções no , e planos respectivamente. n p x p y p z y z x z x yp=(x,y,z)npxpypzyzxzxy

Por um lado, , , e , pelas propriedades básicas da entropia.H[p]=logn H [ p y ] log n y H [ p z ] log n zH[px]lognxH[py]lognyH[pz]lognz

Por outro lado, temos e também adição das três últimas equações nos dá: , onde usamos o fato de que o condicionamento diminui a entropia (em geral, para quaisquer variáveis ​​aleatórias ).H [ p x ] = H [ y ] + H [ z | y ] H [ p y ] = H [ x ] + H [ z | x ] H [

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 [ p x ] + H [ p y ] + H [ p z ] = 2 H [ x ] + H [ y ] + H [ y | x ] + H [ z | x ] + H [ z
H[pz]=H[x]+H[y|x]
H[px]+H[py]+H[pz]= 2H[x]+H[y]+ H[y|x]+ H[z|x] 2 H [+H[z|y] 2 H [ p ] H [ a ] H [ a | b ] a , b2H[x]+2H[y|x]+2H[z|x,y]= 2H[p]H[a]H[a|b]a,b

Portanto, temos ou .n 2n x n y n z2lognlognx+logny+lognzn2nxnynz

arnab
fonte
6
Um artigo relacionado a ser conferido é 'Hipergráficos, Entropia e Desigualdades', de Ehud Friedgut. Ele mostra como uma perspectiva de entropia, especificamente o Lema de Shearer generalizado, pode facilmente recuperar muitas desigualdades padrão, e também algumas não-padrão e de aparência complicada. Eu acho que dá uma perspectiva esclarecedora. Link: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf
Andy Drucker
26

p(LR,E)vL(d(v)!)1/d(v)

  • Selecione uma combinação perfeita uniformemente. A entropia dessa variável é .MH(M)=logp
  • Para , vamos ser o vértice em que é compensada com em .vLXvRvM
  • A variável tem as mesmas informações que , então .X=(Xv:vL)MH(M)=H(X)
  • Idéia inteligente 1: Ao selecionar aleatoriamente (e uniformemente) uma ordem em , Radhakrishnan fornece uma "regra de cadeia aleatória" declarando .LH(X)=vLH(Xv|Xu:u<v,)
  • A partir das informações nas condições ( ), podemos determinar(aproximadamente: o número de opções para a correspondência de ).Xu:u<v,Nv=|N(v)Xu:u<v|v
  • Como é determinado com base nessas informações, a entropia condicionada não muda na igualdade . H ( X vNvH(Xv|Xu:u<v,)=H(Xv|Xu:u<v,,Nv)
  • Idéia inteligente 2: "esquecendo" as informações , só podemos aumentar a entropia: .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)).
  • O resultado segue combinando todas as desigualdades e obtendo expoentes.

GvV(G)(d(v)!)1/2d(v)

Derrick Stolee
fonte
11
H(XvNv)H(XvNv=i)logi
Você está absolutamente correto e eu editei a resposta para usar uma desigualdade.
Derrick Stolee
20

Exemplos muito bons estão contidos em dois artigos de Pippenger, Um Método Teórico da Informação em Teoria Combinatória. J. Comb. Teoria, Ser. A 23 (1): 99-104 (1977) e Entropia e enumeração de funções booleanas. IEEE Transactions on Information Theory 45 (6): 2096-2100 (1999). Na verdade, vários trabalhos de Pippenger contêm provas fofas de fatos combinatórios por meio de entropia / informação mútua. Além disso, os dois livros: Jukna, Combinatória Extremal Com Aplicações em Ciência da Computação e Aigner, Pesquisa Combinatória têm alguns bons exemplos. Também gosto dos dois artigos que Madiman et al. Desigualdades teóricas da informação em combinações aditivas e Terence Tao, estimativas do subconjunto Entropy (você pode encontrá-las no Google Scholar). Espero que ajude.

Ugo
fonte
Parece uma ótima lista de leitura!
Dana Moshkovitz 03/11/19
17

Outro ótimo exemplo é a prova alternativa de Terry Tao do lema de regularidade do gráfico de Szemerédi . Ele usa uma perspectiva teórica da informação para provar uma versão forte do lema da regularidade, que acaba sendo extremamente útil em sua prova do lema da regularidade para hipergráficos . A prova de Tao é, de longe, a prova mais concisa para o lema da regularidade do hipergrafo.

Deixe-me tentar explicar em um nível muito alto essa perspectiva teórica da informação.

GV1V2V1×V2Gρ=|E|/|V1||V2|GϵU1V1U2V2U1U2ρ±ϵ|U1||U2|/|V1||V2|

x1V1x2V2ϵU1,U2ϵGx1U1x2U2(x1,x2)Gx1U1x2U2(x1,x2)

V1V2U1V1,U2V2U1×U2ϵx1x2E(x1,x2)U1(x1)U2(x2)U1U2Ex1|U1x2|U2x1x2

arnab
fonte
15

Basicamente, existe todo um curso dedicado a essa pergunta:

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

O curso ainda está em andamento. Portanto, nem todas as notas estão disponíveis na hora de escrever isso. Além disso, alguns exemplos do curso já foram mencionados.

Moritz
fonte
3
bom ponteiro: parece uma ótima aula.
Suresh Venkat
11
Até onde eu sei, essa oferta é meio curso, com notas contendo alguns exemplos que dão boas respostas à minha pergunta e meio seminário, cobrindo exemplos como limites inferiores de comunicação, extratores, repetição paralela etc., que exigem muito mais do que apenas teoria da informação (aqui não há notas, apenas links para os artigos originais).
Dana Moshkovitz
7

n2d1±ϵdO(logn/ϵ2)Ω(logn/(ϵ2log(1/ϵ)))log(1/ϵ)

ilyaraz
fonte
4
1d
Parece muito natural e agradável que esses resultados puramente geométricos tenham sido comprovados pelas pessoas da TCS!
Ilyaraz 06/12
6

mu[m]x[m]x=utt

O(m1/t)logmuti[t](logm)/tiu

X[m]H[X]=logmX1,,XttH[X]=H[X1]+H[X2|X1]++H[Xt|X1,,Xt1]tlogsssm1/t

t>1

arnab
fonte
5

PPO(log|X|)XP

Gil Kalai
fonte
3

Análise de casos médios de algoritmos usando a complexidade de Kolmogorov por Jiang, Li, Vitanyi.

'Analisar a complexidade média dos algoritmos é um problema muito prático, mas muito difícil na ciência da computação. Nos últimos anos, demonstramos que a complexidade de Kolmogorov é uma ferramenta importante para analisar a complexidade de casos médios de algoritmos. Nós desenvolvemos o método de incompressibilidade [7]. Neste artigo, usamos vários exemplos simples para demonstrar ainda mais o poder e a simplicidade desse método. Provamos limites no número médio de pilhas (filas) necessárias para classificar Queueusort sequencial ou paralelo ou Stacksort. '

Veja também, por exemplo, a complexidade de Kolmogorov e um problema de triângulo do tipo Heilbronn .

Neal Young
fonte
3

A equivalência de amostragem e pesquisa por Scott Aaronson. Aqui ele mostra a equivalência do problema de amostragem e pesquisa na teoria da complexidade em relação à validade da Tese Estendida de Church-Turing. Teoria da informação padrão, teoria da informação algorítmica e complexidade de Kolmogorov são usadas de maneira fundamental.

Ele enfatiza:
" Vamos enfatizar que não estamos usando a complexidade de Kolmogorov apenas como uma conveniência técnica ou como uma abreviação para um argumento de contagem. Em vez disso, a complexidade de Kolmogorov parece essencial mesmo para definir um problema de pesquisa .. "

DurgaDatta
fonte
0

Essa é simples e também uma aproximação: quantas combinações de 10 6 de 10 9 , permitindo duplicatas? A fórmula correta é

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

Mas imagine dar instruções para caminhar ao longo de uma fileira de bilhões de baldes, jogando um milhão de bolas de gude nos baldes ao longo do caminho. Haverá ~ 10 9 "instruções para o próximo balde" e 10 6 instruções "drop a marble". A informação total é

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

que é uma maneira engraçada, mas bastante boa, de aproximar a contagem (log da) Eu gosto porque funciona se eu esquecer como fazer combinações. É equivalente a dizer que

(a + b)! / uma! b! A = b (a + b) (a + b) / a a b b

que é como usar a aproximação de Stirling, cancelar e perder algo.

FutureNerd
fonte
2
Isso pode ser mais legível se você fizer o limite geral em vez de números específicos. Eu acho que você está falando sobre a aproximação baseada no entropia do volume de uma bola de Hamming.
Sasho Nikolov