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

¿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 1 ⊕ x j 2 . Entonces m es al menos exponencial en n, donde el exponente depende linealmente de la relación promedio de $x_1,...,x_m$$n$$i$$k_i$$j_1,j_2$

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.

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.

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 2 ≤ n x n y n z .$n$$\mathbb{R}^3$$n_x$$yz$$n_y$$xz$$n_z$$xy$$n^2 \leq n_x n_y n_z$

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)$$n$$p_x$$p_y$$p_z$$yz$$xz$$xy$

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] = \log n$$H[p_x] \leq \log n_x$$H[p_y] \leq \log n_y$$H[p_z] \leq \log n_z$

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

$2 \log n \leq \log n_x + \log n_y + \log n_z$$n^2 \leq n_x n_y n_z$

$p$$(L\cup R, E)$$\prod_{v \in L} (d(v)!)^{1/d(v)}$

• $M$$H(M) = \log p$
• $v \in L$$X_v$$R$$v$$M$
• $X = (X_v : v \in L)$$M$$H(M) = H(X)$
• $\leq$$L$$H(X) = \sum_{v\in L} H(X_v | { X_u : u < v }, \leq)$
• ${X_u : u < v}, \leq$$N_v = |N(v) \setminus { X_u : u < v }|$$v$
• $N_v$$H(X_v | { X_u : u < v }, \leq) = H(X_v | { X_u : u < v }, \leq, N_v)$
• ${X_u : u < v}, \leq$$H(X_v | { X_u : u < v }, \leq, N_v) \leq H(X_v | N_v)$
• $N_v$${1,\dots, d(v)}$
• $H(X_v | N_v)$$N_v$$H(X_v | N_v) = \sum_{i=1}^{d(v)} \frac{1}{d(v)}H(X_v|N_v=i) \leq \frac{1}{d(v)}\sum_{i=1}^{d(v)}\log i = \log((d(v)!)^{1/d(v)}).$
• El resultado sigue combinando todas las desigualdades y tomando exponentes.

$G$$\prod_{v \in V(G)} (d(v)!)^{1/2d(v)}$

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.

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.

$G$$V_1$$V_2$$V_1 \times V_2$$G$$\rho = |E|/|V_1||V_2|$$G$$\epsilon$$U_1 \subseteq V_1$$U_2 \subseteq V_2$$U_1$$U_2$$\rho \pm \epsilon |U_1||U_2|/|V_1||V_2|$

$x_1$$V_1$$x_2$$V_2$$\epsilon$$U_1, U_2$$\epsilon$$G$$x_1$$U_1$$x_2$$U_2$$(x_1,x_2)$$G$$x_1$$U_1$$x_2$$U_2$$(x_1,x_2)$

$V_1$$V_2$$U_1 \subset V_1, U_2 \subset V_2$$U_1 \times U_2$$\epsilon$$x_1$$x_2$$E(x_1,x_2)$$U_1(x_1)$$U_2(x_2)$$U_1$$U_2$$E$$x_1 | U_1$$x_2 | U_2$$x_1$$x_2$

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.

$n$$\ell_2^d$$1 \pm \epsilon$$d$$O(\log n / \epsilon^2)$$\Omega(\log n / (\epsilon^2 \log(1 / \epsilon)))$$\sim \log(1 / \epsilon)$

$m$$u \in [m]$$x \in [m]$$x=u$$t$$t$

$O(m^{1/t})$$\log m$$u$$t$$i \in [t]$$(\log m)/t$$i$$u$

$X$$[m]$$H[X] = \log m$$X_1, \dots, X_t$$t$$H[X] = H[X_1] + H[X_2 | X_1] + \cdots + H[X_t | X_1, \dots, X_{t-1}] \leq t \log s$$s$$s \geq m^{1/t}$

$t > 1$

$P$$P$$O(\log |X|)$$X$$P$

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 .

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 ... "

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

N = (10 ⁶ + 10 ⁹ )! / (10 ⁶ ! 10 ⁹ !) ~ = 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 ⁹ instrucciones ^de "paso al siguiente balde" y 10 ⁶ instrucciones ^de "soltar una canica". La información total es

log ₂ (N) ~ = -10 ⁶ log ₂ (10 ⁶ / (10 ⁶ + 10 ⁹ )) - 10 ⁹ log ₂ (10 ⁹ / (10 ⁶ + 10 ⁹ )) ~ = 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.

Una aplicación reciente muy agradable para dar límites superiores para permutaciones de alta dimensión por Linial y Luria está aquí: http://www.cs.huji.ac.il/~nati/PAPERS/hd_permutations.pdf