Explizite ausgeglichene Matrix

Ist es möglich, eine explizite -Matrix mit zu erstellen , sodass jede -Matrix weniger als ?0 / 1 N 1,5 N 0,499 × N 0,499 N $N \times N$ $0/1$$N^{1.5}$$N^{0.499} \times N^{0.499}$$N^{0.501}$

Oder es ist wahrscheinlich möglich, eine explizite Treffermenge für eine solche Eigenschaft zu erstellen.

Es ist leicht zu erkennen, dass die Zufallsmatrix diese Eigenschaft mit einer Wahrscheinlichkeit hat, die exponentiell nahe bei . Das Mischen von Lemmen mit Expander reicht auch nicht aus, um diese Eigenschaft abzuleiten.$1$

Ich denke, Pseudozufallsgeneratoren, die kombinatorische Rechtecke täuschen, könnten hier helfen, aber sie sind für gleichmäßige Verteilungen ausgelegt, und ich brauche hier grundsätzlich .$B(N^2, N^{-0.5})$

Was Sie suchen, ist ein Ein-Bit-Extraktor für zwei unabhängige Quellen: eine Funktion , so dass vorausgesetzt, X, Y sind Zufallsvariablen mit min -Tropie 0,499 * log (N), E (X, Y) ist fast ausgeglichen.E: [ N] × [ N] → { 0 , 1 }$E:[N]\times [N]\to \{0,1\}$$E:[N]\times [N]\to \{0,1\}$

Es ist ein notorisch schweres Problem. Für die Parameter, die Sie wollen, glaube ich, wurde es von Bourgain gelöst. Siehe hier: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Diese Antwort basiert auf der Idee von Dana in ihrer Antwort oben.

Ich denke, Sie können eine solche Matrix mit verlustbehafteten Kondensatoren aus zwei Quellen konstruieren. Fixiere und sage N = 2 n . Angenommen , Sie haben eine explizite Funktion f ( x , y ) , dass zwei unabhängige Zufallsquellen nimmt ( X , Y ) , die jeweils mit der Länge n , und mit min-Entropie mindestens k = n ( 1 / 2 - δ ) , und gibt eine Sequenz von n ' = n /$\delta = 0.001$$N=2^n$$f(x,y)$$(X, Y)$$n$$k = n(1/2 - \delta)$$n' = n/2$Bits, ist mit min-Entropie wenigstens eine Verteilung -Schließen k ' = n ( 1 / 2 - 3 δ ) . Ich denke, Sie können probabilistische Standardargumente verwenden, um zu zeigen, dass eine Zufallsfunktion diese Eigenschaften erfüllt (mit überwältigender Wahrscheinlichkeit), wenn 2 k > k ′ + log ( 1 / ϵ ) + O ( 1 ) . Das probabilistische Argument sollte ähnlich dem sein, was in der folgenden Veröffentlichung für verlustfreie Kondensatoren und allgemeinere Leiter verwendet wurde:$\epsilon$$k'=n(1/2-3\delta)$$2k > k'+\log(1/\epsilon)+O(1)$

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Randomness Conductors und ständige Expansion über die Degree / 2-Grenze hinaus

In unserem Fall setzen wir , so dass wir sicher sind, dass die von uns benötigte Funktion existiert. Nun wird ein Mittelungs Argument zeigt , dass es eine n " -Bit - String z , so dass die Anzahl der ( x , y ) mit f ( x , y ) = z ist mindestens 2 1,5 n . Angenommen, Sie kennen ein solches z und beheben es (Sie können ein beliebiges z auswählen$\epsilon = 2^{-k'}$$n'$$z$$(x,y)$$f(x,y)=z$$2^{1.5 n}$$z$$z$wenn Sie zusätzlich wissen, dass Ihre Funktion die vollständig gleichmäßige Verteilung auf eine Verteilung abbildet, die fast gleich) ist. Identifizieren Sie nun die Einträge Ihrer N × N- Matrix durch die Möglichkeiten von ( x , y ) und setzen Sie eine 1 an die Position ( x , y ), falls f ( x , y ) = z . Nach unserer Wahl von z hat diese Matrix mindestens 2 1,5 $O(2^{-n/2})$$N \times N$$(x,y)$$1$$(x,y)$$f(x,y)=z$$z$$2^{1.5n}$ Einsen.

Nehmen Sie nun eine beliebige Submatrix und lassen Sie X , Y gleichmäßige Verteilungen auf den ausgewählten Zeilen bzw. Spalten sein. Durch die Wahl von f , wissen wir , dass f ( X , Y ) ist ε -Schließen min-Entropie mit k ' . Wenn wir also einen gleichmäßig zufälligen Eintrag der Submatrix auswählen, beträgt die Wahrscheinlichkeit, eine 1 zu haben, höchstens 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}$. Dies bedeutet, dass Sie nach Wunsch höchstens in der Submatrix haben.$2^{2k-k'+1} = O(2^{n/2 + \delta})$

Natürlich ist es eine sehr herausfordernde Aufgabe, ein explizites mit den gewünschten Parametern (insbesondere einer nahezu optimalen Ausgabelänge) zu finden, und bisher ist keine solche Funktion bekannt.$f$