La théorie de l'information est-elle utilisée pour prouver des déclarations combinatoires ordonnées?

54

Quels sont vos exemples préférés dans lesquels la théorie de l’information est utilisée pour prouver de façon simple une déclaration combinatoire nette?

Certains exemples auxquels je peux penser sont liés aux limites inférieures pour les codes localement décodables, par exemple, dans cet article: supposons que pour un tas de chaînes binaires de longueur il en est de même pour chaque , pour différent paires { },Alors m est au moins exponentiel dans n, où l’exposant dépend linéairement du rapport moyen 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

Un autre exemple (lié) est certaines inégalités isopérimétriques sur le cube booléen (n'hésitez pas à en parler dans vos réponses).

Avez-vous d'autres exemples intéressants? De préférence, court et facile à expliquer.

Dana Moshkovitz
la source
quelqu'un peut-il donner un ref sur "Un autre exemple (lié) est quelques inégalités isopérimétriques sur le cube booléen"?
Vzn

Réponses:

40

La preuve de Moser de la lemma locale constructive de Lovasz . Il montre fondamentalement que, dans les conditions du lemme local, le deuxième algorithme le plus simple pour SAT auquel on puisse penser fonctionne. (La première solution peut être d’essayer simplement une assignation aléatoire jusqu’à ce que celle-ci fonctionne. La deuxième solution consiste à choisir une assignation aléatoire, à trouver une clause non satisfaite, à la satisfaire, puis à voir quelles autres clauses vous avez rompues, rappelées et répétées jusqu’à fin.) La preuve que cela fonctionne en temps polynomial est peut-être l'utilisation la plus élégante de la théorie de l'information (ou de la complexité de Kolmogorov, comme vous voulez l'appeler dans ce cas) que j'ai jamais vue.

Joshua Grochow
la source
1
La belle preuve de complexité de Kolmogorov de Moser est expliquée ici: blog.computationalcomplexity.org/2009/06/… , mais je dois admettre que je recherchais plutôt un type d'exemple d'entropie / information mutuelle / calcul ...
Dana Moshkovitz
Il existe quelques applications assez intéressantes de la complexité de Kolmogorov données en réponse à cette question: cstheory.stackexchange.com/questions/286
arnab
Terry Tao a également discuté de l'argument de Moser sur son blog: terrytao.wordpress.com/2009/08/05/…
Anthony Leverrier
5
En fait, dans son deuxième article (avec Tardos), vous n’avez plus besoin de recourir à la récursivité. Vous recherchez simplement une clause non satisfaite, choisissez une affectation aléatoire pour ses variables et effectuez une itération . C'est ça. Pour une raison quelconque, l'algorithme plus simple (ayant la même analyse) ne s'est pas bloqué.
Yuval Filmus
@DanaMoshkovitz: Je ne sais pas pourquoi cela ne m'est pas venu à l'esprit plus tôt en réponse à votre commentaire: la complexité et l'entropie de Kolmogorov sont, à bien des égards, essentiellement équivalentes. Voir, par exemple, Hammer-Romaschenko-Shen-Vershchagin: dx.doi.org/10.1006/jcss.1999.1677 . Par exemple, sur la base de [HRSV], la preuve du lemme de Shearer dans arnab peut être prouvée avec essentiellement la même preuve en utilisant la complexité de Kolmogorov à la place de l'entropie. La différence réside simplement dans le point de vue: K concerne la longueur de la description, H ... Parfois, l’un est plus facile / plus naturel que l’autre. pilogpi
Joshua Grochow
33

Mon exemple préféré de ce type est la preuve du lemme de Shearer basée sur l'entropie. (J'ai appris cette preuve et plusieurs autres très jolies grâce à Entropy and Counting de Jaikumar Radhakrishnan .)

Revendication: Supposons que vous avez points dans qui ont projections distinctes sur le plan , projections distinctes sur le plan et projections distinctes sur le plan . Ensuite, .R 3 n x y z n y x z n z x y n 2n x n y n znR3nxyznyxznzxyn2nxnynz

Preuve: Soit un point uniformément choisi au hasard parmi les points. Soit , , ses projections sur les plans , et respectivement. n p x p y p z y z x z x yp=(x,y,z)npxpypzyzxzxy

D'une part, , , et , par les propriétés de base de l'entropie.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

Par contre, nous avons et aussi L'ajout des trois dernières équations nous donne: H [ z | x ] + H [ z | y ] 2 H [ x ] + 2 H [ y | x ] + 2 H [ z | x ,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[pz]=H[x]+H[y|x]
H[px]+H[py]+H[pz]= 2H[x]+H[y]+ H[y|x]+ H[z|x] +H[z|y] 2 H [ p ] , où nous avons utilisé le fait que le conditionnement diminue l'entropie (en général, H [ a ] H [ a | b ] pour toute variable aléatoire a , b ).2H[x]+2H[y|x]+2H[z|x,y]= 2H[p]H[a]H[a|b]a,b

Nous avons donc , ou n 2n x n y n z .2lognlognx+logny+lognzn2nxnynz

arnab
la source
6
Un document connexe à consulter est «Hypergraphes, Entropie et Inégalités» par Ehud Friedgut. Il montre comment une perspective d'entropie, en particulier un lemme de Shearer généralisé, peut facilement récupérer de nombreuses inégalités standard, ainsi que des inégalités complexes et non standard. Je pense que cela donne une perspective éclairante. Lien: ma.huji.ac.il/~ehudf/docs/KKLBKKKL.pdf
Andy Drucker
26

La preuve entropie de Radhakrishnan du théorème de Bregman, que le nombre de couplages parfaits dans un graphe biparti ( L R , E ) est au plus Π v L ( d ( v ) ! ) 1 / d ( v ) . La preuve utilise deux idées très intelligentes. Voici un croquis de la preuve:p(LR,E)vL(d(v)!)1/d(v)

  • Sélectionnez une correspondance parfaite uniformément. L'entropie de cette variable est H ( M ) = log p .MH(M)=logp
  • Pour , que X v soit le sommet de R qui est adapté à v dans M .vLXvRvM
  • La variable a la même information que M , donc H ( M ) = H ( X ) .X=(Xv:vL)MH(M)=H(X)
  • Intelligent Idea 1: Par hasard (uniformément) sélectionner un ordre sur L , Radhakrishnan fournit une "règle de la chaîne aléatoire" indiquant H ( X ) = Σ v L H ( X v | X u : u < v , ) .LH(X)=vLH(Xv|Xu:u<v,)
  • À partir des informations dans les conditions ( ), nous pouvons déterminer N v = | N ( v ) X u : u < v | (à peu près: le nombre de choix pour la correspondance v ).Xu:u<v,Nv=|N(v)Xu:u<v|v
  • Puisque est déterminé à partir de cette information, l'entropie conditionnée ne change pas dans l'égalité H ( X v | X u : u < v , ) = H ( X v | X u : u < v , , N v ) .NvH(Xv|Xu:u<v,)=H(Xv|Xu:u<v,,Nv)
  • Idée intelligente 2: En "oubliant" l'information , on ne peut qu'augmenter l'entropie: H ( X v | X u : u < v , , N v ) H ( X v | N v ) .Xu:u<v,H(Xv|Xu:u<v,,Nv)H(Xv|Nv)
  • Fait fou: La variable est uniformément distribuée sur l’ensemble 1 , , d ( v ) .Nv1,,d(v)
  • Maintenant, pour calculer l'entropie , nous additionnons toutes les valeurs de N v : H ( X v | N v ) = d ( v ) i = 1 1H(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)).
  • Le résultat est ensuite obtenu en combinant toutes les inégalités et en prenant des exposants.

La généralisation de cette inégalité est Kahn-Lovász Théorème: Le nombre de appariements parfaits dans tout graphe est au plus Π v V ( G ) ( d ( v ) ! ) 1 / 2 d ( v ) . Une preuve d'entropie de ce résultat a été prouvée par Cutler et Radcliffe .GvV(G)(d(v)!)1/2d(v)

Derrick Stolee
la source
1
H(XvNv)H(XvNv=i)logi
Vous avez absolument raison et j'ai modifié la réponse pour utiliser une inégalité.
Derrick Stolee
20

De très bons exemples sont contenus dans deux articles de Pippenger. Une méthode de la théorie de l'information en théorie combinatoire. J. Comb. Théorie, Ser. A 23 (1): 99-104 (1977) et Entropie et énumération des fonctions booléennes. Transactions IEEE sur la théorie de l'information 45 (6): 2096-2100 (1999). En fait, plusieurs articles de Pippenger contiennent de jolies preuves de faits combinatoires par entropie / information mutuelle. En outre, les deux livres: Jukna, La combinatoire extrême avec des applications en informatique et Aigner, La recherche combinatoire en ont de bons exemples. J'aime aussi les deux papiers Madiman et al. Inégalités de la théorie de l'information dans la combinatoire additive et Terence Tao, estimations du jeu d'entropie (vous pouvez les trouver avec Google Scholar). J'espère que ça aide.

Ugo
la source
On dirait une excellente liste de lecture!
Dana Moshkovitz
17

Un autre bon exemple est la preuve alternative de Terry Tao du lemme de régularité des graphes de Szemerédi . Il utilise une perspective théorique de l'information pour prouver une version forte du lemme de régularité, ce qui s'avère extrêmement utile pour prouver le lemme de régularité des hypergraphes . La preuve de Tao est de loin la preuve la plus concise pour le lemme de régularité de l'hypergraphe.

Permettez-moi d'essayer d'expliquer à un très haut niveau cette perspective de la théorie de l'information.

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
la source
15

Il existe essentiellement un cours entier consacré à cette question:

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

Le cours est toujours en cours. Toutes les notes ne sont donc pas disponibles au moment de la rédaction. En outre, certains exemples du cours ont déjà été mentionnés.

Moritz
la source
3
joli pointeur: ressemble à une grande classe.
Suresh Venkat
1
Pour autant que je sache, cette offre est à moitié cours, avec des notes contenant des exemples qui apportent de bonnes réponses à ma question, et un demi-séminaire, couvrant des exemples tels que la communication, les extracteurs, la répétition parallèle, etc., nécessitant bien plus que la simple la théorie de l'information (ici, pas de notes, juste des liens vers les papiers d'origine).
Dana Moshkovitz
7

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

ilyaraz
la source
4
1d
Il semble très naturel et agréable que ces résultats purement géométriques aient été prouvés par les gens 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

arnab
la source
5

PPO(log|X|)XP

Gil Kalai
la source
3

Analyse de cas moyens d'algorithmes utilisant la complexité de Kolmogorov par Jiang, Li, Vitanyi.

«L'analyse de la complexité moyenne des algorithmes est un problème très pratique mais très difficile en informatique. Ces dernières années, nous avons démontré que la complexité de Kolmogorov est un outil important pour l'analyse de la complexité moyenne des cas des algorithmes. Nous avons développé la méthode d'incompressibilité [7]. Dans cet article, nous utilisons plusieurs exemples simples pour démontrer davantage la puissance et la simplicité de cette méthode. Nous prouvons des bornes sur le nombre moyen de cas de piles (files d'attente) nécessaires au tri séquentiel ou parallèle de Queueusort ou Stacksort. '

Voir aussi, par exemple, la complexité de Kolmogorov et un problème triangulaire de type Heilbronn .

Neal Young
la source
3

L'équivalence de l'échantillonnage et de la recherche par Scott Aaronson. Il montre ici l’équivalence des problèmes d’échantillonnage et de recherche dans la théorie de la complexité en ce qui concerne la validité de la thèse étendue de Church-Turing. La théorie de l'information standard, la théorie de l'information algorithmique et la complexité de Kolmogorov sont utilisées de manière fondamentale.

Il souligne:
" Soulignons que nous n'utilisons pas la complexité de Kolmogorov uniquement pour des raisons de commodité technique, ni pour abréger un argument de comptage. Au contraire, la complexité de Kolmogorov semble essentielle même pour définir un problème de recherche .. "

DurgaDatta
la source
0

Celui-ci est simple et approximatif: combien de combinaisons de 10 6 choses sur 10 9 , permettant des doublons? La bonne formule est

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

Mais imaginez donner des instructions pour marcher le long d'une rangée de milliards de seaux, laissant tomber un million de billes dans les seaux le long du chemin. Il y aura ~ 10 9 instructions "Pas à pas vers le seau suivant" et 10 6 instructions "Laisser tomber une bille". L'information totale est

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

ce qui est drôle, mais très bon moyen d’approximer le (journal du) compte. J'aime ça parce que ça marche si j'oublie comment faire de la combinatoire. Cela équivaut à dire que

(a + b)! / une! b! ~ = (a + b) (a + b) / a a b b

ce qui revient à utiliser l'approximation de Stirling, à annuler et à rater quelque chose.

FutureNerd
la source
2
Cela peut être plus lisible si vous faites la borne générale plutôt que des nombres spécifiques. Je pense que vous parlez de l'approximation basée sur l'entropie du volume d'une balle de Hamming.
Sasho Nikolov