¿Teoría de la información utilizada para probar afirmaciones combinatorias ordenadas?

54

¿Cuáles son sus ejemplos favoritos donde la teoría de la información se usa para probar una declaración combinatoria ordenada de una manera simple?

Algunos ejemplos que se me ocurren se relacionan con los límites para disminuir localmente códigos descifrables, por ejemplo, en este documento: supongamos que para un montón de cadenas binarias de longitud n sostiene que para cada i , para k i diferentes pares { j 1 , j 2 }, e i = x j 1x j 2 . Entonces m es al menos exponencial en n, donde el exponente depende linealmente de la relación promedio de kx1,...,xmnikij1,j2

ei=xj1xj2.
.ki/m

Otro ejemplo (relacionado) son algunas desigualdades isoperimétricas en el cubo booleano (siéntase libre de explicar esto en sus respuestas).

¿Tienes más buenos ejemplos? Preferiblemente, corto y fácil de explicar.

Dana Moshkovitz
fuente
¿Alguien puede dar una referencia a "Otro ejemplo (relacionado) son algunas desigualdades isoperimétricas en el cubo booleano"?
vzn

Respuestas:

40

La prueba de Moser del constructivo Lema local de Lovasz . Básicamente muestra que, bajo las condiciones del lema local, el segundo algoritmo más simple para SAT que se te ocurra funciona. (La primera más simple podría ser simplemente intentar una asignación aleatoria hasta que una funcione. La segunda más simple es elegir una asignación aleatoria, encontrar una cláusula insatisfecha, satisfacerla, luego ver qué otras cláusulas rompió, repetir y repetir hasta que esté listo). La prueba de que esto se ejecuta en tiempo polinómico es quizás el uso más elegante de la teoría de la información (o la complejidad de Kolmogorov, como quiera llamarlo en este caso) que he visto.

Joshua Grochow
fuente
1
La hermosa prueba de complejidad de Mosmo de Kolmogorov se explica aquí: blog.computationalcomplexity.org/2009/06/… , pero debo admitir que estaba buscando más un tipo de ejemplo de entropía / información mutua / cálculo ...
Dana Moshkovitz el
Hay algunas aplicaciones bastante interesantes de la complejidad de Kolmogorov dadas como respuestas a esta pregunta: cstheory.stackexchange.com/questions/286
arnab
Terry Tao también discutió el argumento de Moser en su blog: terrytao.wordpress.com/2009/08/05/…
Anthony Leverrier
55
En realidad, en su segundo artículo (con Tardos) ya no necesita recurrir a la recursividad. Simplemente busca una cláusula insatisfecha, elige una asignación aleatoria para sus variables e itera . Eso es. Por alguna razón, el algoritmo más simple (que tiene el mismo análisis) no se ha pegado.
Yuval Filmus
@DanaMoshkovitz: No sé por qué esto no se me ocurrió decir antes en respuesta a tu comentario: la complejidad y la entropía de Kolmogorov son, en muchos sentidos, esencialmente equivalentes. Véase, por ejemplo, Hammer-Romaschenko-Shen-Vershchagin: dx.doi.org/10.1006/jcss.1999.1677 . Por ejemplo, basado en [HRSV], la prueba del Lemma de Shearer en la respuesta de arnab puede probarse esencialmente con la misma prueba usando la complejidad de Kolmogorov en lugar de la entropía. La diferencia es solo el punto de vista: K es sobre la longitud de la descripción, H es sobre ... A veces uno es más fácil / más natural que el otro. pilogpi
Joshua Grochow
33

Mi ejemplo favorito de este tipo es la prueba basada en entropía del Lema de Shearer. (Aprendí de esta prueba y varias otras muy bonitas de Entropy and Counting de Jaikumar Radhakrishnan ).

Reclamación: suponga que tiene puntos en R 3 que tienen n x proyecciones distintas en el plano y z , n y proyecciones distintas en el plano x z y n z proyecciones distintas en el plano x y . Entonces, n 2n x n y n z .nR3nxyznyxznzxyn2nxnynz

Prueba: Sea un punto uniformemente elegido al azar de los n puntos. Supongamos que p x , p y , p z denotan sus proyecciones en los planos y z , x z y x y respectivamente. p=(x,y,z)npxpypzyzxzxy

Por un lado, , H [ p x ] log n x , H [ p y ] log n y y H [ p z ] log n z , por las propiedades básicas de la entropía.H[p]=lognH[px]lognxH[py]lognyH[pz]lognz

Por otro lado, tenemos y también H [ p x ] = H [ y ] + H [ z | y ] H [ p y ] = H [ x ] + H [ z

H[p]=H[x]+H[y|x]+H[z|x,y]
H[px]=H[y]+H[z|y]
H [ p z ] = H [ x ] + H [ y | x ] Agregar las últimas tres ecuaciones nos da: H [ p x ] + H [ p y ] + H [ p z ] = 2 H [ x ] + H [ y ] + H [ y | x ] + H
H[py]=H[x]+H[z|x]
H[pz]=H[x]+H[y|x]
H[px]+H[py]+H[pz]= 2H[x]+H[y]+ H[y|x]+ + H [ z | y ] 2 H [ x ] + 2 H [ y | x ] + 2 H [ z | x , y ] = 2 H [ p ] , donde usamos el hecho de que el condicionamiento disminuye la entropía (en general, H [ a ] H [ a | b ]H[z|x] +H[z|y] 2H[x]+2H[y|x]+2H[z|x,y]= 2H[p]H[a]H[a|b]para cualquier variable aleatoria ).a,b

2lognlognx+logny+lognzn2nxnynz

arnab
fuente
66
Un artículo relacionado para revisar es 'Hipergrafías, entropía y desigualdades' de Ehud Friedgut. Muestra cómo una perspectiva de entropía, específicamente un Lema de Shearer generalizada, puede recuperar fácilmente muchas desigualdades estándar, y también algunas no estándar, de aspecto complicado. Creo que da una perspectiva esclarecedora. Enlace: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf
Andy Drucker el
26

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

  • MH(M)=logp
  • vLXvRvM
  • X=(Xv:vL)MH(M)=H(X)
  • 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)
  • 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)).
  • El resultado sigue combinando todas las desigualdades y tomando exponentes.

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

Derrick Stolee
fuente
1
H(XvNv)H(XvNv=i)logi
Tienes toda la razón y he editado la respuesta para usar una desigualdad.
Derrick Stolee el
20

Muy buenos ejemplos están contenidos en dos documentos de Pippenger Un método teórico de la información en la teoría combinatoria. J. Comb. Teoría, Ser. A 23 (1): 99-104 (1977) y Entropía y enumeración de funciones booleanas. IEEE Transactions on Information Theory 45 (6): 2096-2100 (1999). En realidad, varios documentos de Pippenger contienen lindas pruebas de hechos combinatorios por medio de entropía / información mutua. Además, los dos libros: Jukna, Extremal Combinatorics With Applications in Computer Science y Aigner, Combinatorial Search tienen algunos buenos ejemplos. También me gustan los dos artículos Madiman et al. Desigualdades teóricas de la información en combinatoria aditiva y Terence Tao, estimaciones de suma de entropía (puede encontrarlas con Google Scholar). Espero eso ayude.

Ugo
fuente
¡Parece una gran lista de lectura!
Dana Moshkovitz
17

Otro gran ejemplo es la prueba alternativa de Terry Tao del lema de regularidad del gráfico Szemerédi . Utiliza una perspectiva teórica de la información para probar una versión sólida del lema de regularidad, que resulta ser extremadamente útil en su prueba del lema de regularidad para las hipergrafías . La prueba de Tao es, con diferencia, la prueba más concisa del lema de regularidad del hipergrama.

Permítanme tratar de explicar a un nivel muy alto esta perspectiva teórica de la información.

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

revs arnab
fuente
15

Básicamente hay un curso completo dedicado a esta pregunta:

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

El curso aún está en curso. Por lo tanto, no todas las notas están disponibles al momento de escribir esto. Además, ya se mencionaron algunos ejemplos del curso.

Moritz
fuente
3
Buen puntero: parece una gran clase.
Suresh Venkat
1
Por lo que puedo decir, esta oferta es de medio curso, con notas que contienen algunos ejemplos que responden bien a mi pregunta, y medio seminario, que abarca ejemplos como límites inferiores de comunicación, extractores, repetición paralela, etc., que requieren mucho más que solo teoría de la información (aquí no hay notas, solo enlaces a los documentos originales).
Dana Moshkovitz
7

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

ilyaraz
fuente
44
1d
¡Parece muy natural y agradable que estos resultados puramente geométricos hayan sido probados por personas de TCS!
ilyaraz
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

revs arnab
fuente
5

PPO(log|X|)XP

Gil Kalai
fuente
3

Análisis de casos promedio de algoritmos utilizando la complejidad de Kolmogorov por Jiang, Li, Vitanyi.

'Analizar la complejidad promedio de los algoritmos es un problema muy práctico pero muy difícil en informática. En los últimos años hemos demostrado que la complejidad de Kolmogorov es una herramienta importante para analizar la complejidad promedio de los algoritmos. Hemos desarrollado el método de incompresibilidad [7]. En este artículo usamos varios ejemplos simples para demostrar aún más el poder y la simplicidad de dicho método. Probamos límites en el número promedio de mayúsculas y minúsculas (colas) requeridas para ordenar Queueusort o Stacksort secuenciales o paralelas '.

Véase también, por ejemplo, la complejidad de Kolmogorov y un problema triangular del tipo Heilbronn .

Neal Young
fuente
3

La equivalencia de muestreo y búsqueda por Scott Aaronson. Aquí muestra la equivalencia del problema de muestreo y búsqueda en la teoría de la complejidad con respecto a la validez de la tesis extendida de Church-Turing. La teoría de la información estándar, la teoría de la información algorítmica y la complejidad de Kolmogorov se utilizan de manera fundamental.

Él enfatiza:
" Hagamos hincapié en que no estamos usando la complejidad de Kolmogorov como una simple conveniencia técnica, o como una abreviatura para un argumento de conteo. Más bien, la complejidad de Kolmogorov parece esencial incluso para definir un problema de búsqueda ... "

DurgaDatta
fuente
0

Este es simple y también una aproximación: ¿cuántas combinaciones de 10 6 cosas de 10 9 , permitiendo duplicados? La fórmula correcta es

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

Pero imagine dar instrucciones para caminar a lo largo de una fila de mil millones de cubos, dejando caer un millón de canicas en los cubos a lo largo del camino. Habrá ~ 10 9 instrucciones de "paso al siguiente balde" y 10 6 instrucciones de "soltar una canica". La información total es

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 es una forma divertida, pero bastante buena, de aproximar el (registro del) recuento. Me gusta porque funciona si olvido cómo hacer combinatoria. Es equivalente a decir que

(a + b)! / ¡una! ¡si! ~ = (a + b) (a + b) / a a b b

que es como usar la aproximación de Stirling, cancelar y perder algo.

FutureNerd
fuente
2
Esto puede ser más legible si hace el límite general en lugar de números específicos. Creo que estás hablando de la aproximación basada en entropía del volumen de una bola de Hamming.
Sasho Nikolov