Matrice explicite équilibrée

20

Est - il possible de construire un explicite 0 / 1 matrix avec N 1,5 ceux de telle sorte que tous les N 0,499 × N 0,499 sous - matrice contient moins de N 0,501 celles?N×N 0/1N1.5N0.499×N0.499N0.501

Ou il est probablement possible de construire un ensemble de frappes explicites pour une telle propriété.

Il est facile de voir qu'une matrice aléatoire a cette propriété avec une probabilité exponentiellement proche de . De plus, un lemme de mélange d'expanseur n'est pas suffisant pour dériver cette propriété.1

J'imagine que des générateurs pseudo-aléatoires qui trompent les rectangles combinatoires pourraient aider ici, mais ils sont conçus pour des distributions uniformes et j'ai essentiellement besoin de ici.B(N2,N0.5)

ilyaraz
la source
5
C'est une question intéressante: je suis curieux de connaître la motivation.
Suresh Venkat
@Suresh Il provient de la non-extractibilité quantitative des informations mutuelles. Si vous êtes intéressé, je peux élaborer.
ilyaraz
Je le suis vraiment. vous pouvez m'envoyer un e-mail ([email protected]) si c'est plus simple de cette façon.
Suresh Venkat

Réponses:

11

Ce que vous recherchez est un extracteur à un bit pour deux sources indépendantes: une fonction , de sorte que, à condition que X, Y soient des variables aléatoires avec une entropie min 0,499 * log (N), E (X, Y) est presque équilibré.E:[N]×[N]{0,1}

C'est un problème difficile notoire. Pour les paramètres que tu veux, je crois que ça a été résolu par Bourgain. Voir ici: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Dana Moshkovitz
la source
1
Bourgain donne un biais pour certains α > 0 . Je ne suis pas sûr que l'analyse peut donner α = 1 / 2 . Si j'étais vous, je l'étudierais et vérifierais. Vous pouvez également demander à Anup Rao, Zeev Dvir, Avi Wigderson ou à toute autre personne ayant travaillé sur ce problème. p=Nαα>0α=1/2
Dana Moshkovitz
7
@ilyaraz: Lorsque vous (ou n'importe qui) découvrez si la construction de Bourgain donne ou non la matrice souhaitée, veuillez partager (sauf si cela vous dérange)!
Tsuyoshi Ito
1
cela a été un Q&A très intéressant. J'appuie la demande de Tsuyoshi.
Suresh Venkat
2
En relisant la question et la réponse (il y a un certain temps ..), je pense que je n'ai pas remarqué que le questionneur n'en voulait que N ^ {1,5}, ce qui correspond à extraire un bit qui est 1 avec la probabilité N ^ {-0,5} plutôt qu'un bit équilibré. Néanmoins, je pense que la référence aux extracteurs à deux sources est utile. Je peux imaginer que des techniques similaires seraient utiles pour le réglage de la question.
Dana Moshkovitz
1
1) Si un extracteur produit k bits presque uniformes, alors, en particulier, vous pouvez obtenir un bit égal à 1 avec une probabilité ~ 1/2/2 k. 2) C'est assez inutile, et cela me semble être une belle question de recherche pour trouver un moyen plus efficace de générer de tels bits.
Dana Moshkovitz
2

Cette réponse est basée sur l'idée de Dana dans sa réponse ci-dessus.

Je pense que vous pouvez construire une telle matrice en utilisant des condenseurs à perte à deux sources. Fixez et dites N = 2 n . Supposons que vous avez une fonction explicite f ( x , y ) qui prend les deux sources aléatoires indépendantes ( X , Y ) , chacune de longueur n et ayant min-entropie au moins k = n ( une / 2 - δ ) et délivre en sortie une séquence de n = n / 2δ=0.001N=2nf(x,y)(X,Y)nk=n(1/2δ)n=n/2bits qui est -Fermer à une distribution d'entropie min avec au moins k ' = n ( 1 / deux - trois δ ) . Je pense que vous pouvez utiliser des arguments probabilistes standard pour montrer qu'une fonction aléatoire satisfait ces propriétés (avec une probabilité écrasante) si 2 k > k + log ( 1 / ϵ ) + O ( 1 ) . L'argument probabiliste devrait être similaire à celui utilisé dans l'article suivant pour les condenseurs sans perte et les conducteurs plus généraux:ϵk=n(1/23δ)2k>k+log(1/ϵ)+O(1)

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Conducteurs aléatoires et expansion à degré constant au-delà de la barrière de degré / 2

Dans notre cas, nous posons , donc nous sommes sûrs de l'existence de la fonction dont nous avons besoin. Maintenant, un argument de calcul de moyenne montre qu'il existe un n ' bits chaîne z de telle sorte que le nombre de ( x , y ) avec f ( x , y ) = z est d' au moins 2 1,5 n . Supposons que vous connaissiez un tel z et corrigez-le (vous pouvez choisir n'importe quel z arbitraireϵ=2knz(x,y)f(x,y)=z21.5nzzsi vous savez en outre que votre fonction mappe la distribution entièrement uniforme sur une distribution qui est -close sur uniforme). Identifiez maintenant les entrées de votre matrice N × N par les possibilités de ( x , y ) et mettez 1 à la position ( x , y ) si f ( x , y ) = z . Par notre choix de z , cette matrice a au moins 2 1,5 nO(2n/2)N×N(x,y)1(x,y)f(x,y)=zz21.5n ceux.

Maintenant, prenez n'importe quelle sous-matrice de et laissez X , Y des distributions uniformes sur les lignes et les colonnes choisies, respectivement. Par le choix de f , on sait que f ( X , Y ) est ϵ- proche d'avoir une entropie min k ' . Par conséquent, si nous choisissons une entrée uniformément aléatoire de la sous-matrice, la probabilité d'avoir un 1 est au plus 2 - k + ϵ 2 - k + 12k×2kX,Yff(X,Y)ϵk12k+ϵ2k+1. Cela signifie que vous avez au plus ceux dans la sous-matrice, comme vous le souhaitez.22kk+1=O(2n/2+δ)

Bien sûr, trouver un f explicite avec les paramètres souhaités (en particulier, une longueur de sortie presque optimale) est une tâche très difficile et aucune fonction de ce type n'est connue à ce jour.f

MCH
la source