Matrice explicite équilibrée

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 \times N$ $0/1$$N^{1.5}$$N^{0.499} \times N^{0.499}$$N^{0.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(N^2, N^{-0.5})$

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 }$E:[N]\times [N]\to \{0,1\}$$E:[N]\times [N]\to \{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

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 /$\delta = 0.001$$N=2^n$$f(x,y)$$(X, Y)$$n$$k = n(1/2 - \delta)$$n' = n/2$bits 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:$\epsilon$$k'=n(1/2-3\delta)$$2k > k'+\log(1/\epsilon)+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$\epsilon = 2^{-k'}$$n'$$z$$(x,y)$$f(x,y)=z$$2^{1.5 n}$$z$$z$si 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 $O(2^{-n/2})$$N \times N$$(x,y)$$1$$(x,y)$$f(x,y)=z$$z$$2^{1.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 ′ + $2^k \times 2^k$$X, Y$$f$$f(X,Y)$$\epsilon$$k'$$1$$2^{-k'}+\epsilon\leq 2^{-k'+1}$. Cela signifie que vous avez au plus ceux dans la sous-matrice, comme vous le souhaitez.$2^{2k-k'+1} = O(2^{n/2 + \delta})$

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$