Explizite ausgeglichene Matrix

20

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 0,501N×N 0/1N1.5N0.499×N0.499N0.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(N2,N0.5)

Ilyaraz
quelle
5
Das ist eine interessante Frage: Ich bin gespannt auf die Motivation.
Suresh Venkat
@Suresh Es kommt von der quantitativen Nichtextrahierbarkeit von gegenseitigen Informationen. Wenn Sie interessiert sind, kann ich näher darauf eingehen.
Ilyaraz
Ich bin es tatsächlich. Sie können mir eine E-Mail senden ([email protected]), wenn dies einfacher ist.
Suresh Venkat

Antworten:

11

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}

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

Dana Moshkovitz
quelle
1
Bourgain gibt Bias für einige . Ich bin nicht sicher, ob die Analyse . Wenn ich du wäre, würde ich es studieren und nachsehen. Sie können auch Anup Rao, Zeev Dvir, Avi Wigderson oder eine der anderen Personen fragen, die an diesem Problem gearbeitet haben. α > 0 α = 1 / 2p=Nαα>0α=1/2
Dana Moshkovitz
7
@ilyaraz: Wenn Sie (oder jemand) herausfinden, ob die Konstruktion von Bourgain eine gewünschte Matrix ergibt oder nicht, teilen Sie dies bitte mit (es sei denn, es macht Ihnen etwas aus)!
Tsuyoshi Ito
1
Dies war eine sehr interessante Frage und Antwort. Ich werde Tsuyoshis Bitte nachkommen.
Suresh Venkat
2
Wenn ich die Frage und Antwort noch einmal lese (es ist eine Weile her ..), glaube ich, dass ich nicht bemerkt habe, dass der Fragesteller nur N ^ {1.5} wollte, was dem Extrahieren eines Bits mit der Wahrscheinlichkeit N ^ von 1 entspricht {-0.5} statt eines ausgeglichenen Bits. Trotzdem halte ich den Hinweis auf Zwei-Quellen-Extraktoren für hilfreich. Ich kann mir vorstellen, dass ähnliche Techniken für die Fragestellung nützlich wären.
Dana Moshkovitz
1
1) Wenn ein Extraktor k nahezu gleichförmige Bits ausgibt, können Sie insbesondere ein Bit erhalten, das mit einer Wahrscheinlichkeit von ~ 1/2 ^ k 1 ist. 2) Das ist ziemlich verschwenderisch, und es klingt für mich wie eine nette Forschungsfrage, effizientere Methoden zu finden, um solche Bits zu generieren.
Dana Moshkovitz
2

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 / 2δ=0.001N=2nf(x,y)(X,Y)nk=n(1/2δ)n=n/2Bits, 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:ϵk=n(1/23δ)2k>k+log(1/ϵ)+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ϵ=2knz(x,y)f(x,y)=z21.5nzzwenn 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 nO(2n/2)N×N(x,y)1(x,y)f(x,y)=zz21.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 ' + 12k×2kX,Yff(X,Y)ϵk12k+ϵ2k+1. Dies bedeutet, dass Sie nach Wunsch höchstens in der Submatrix haben.22kk+1=O(2n/2+δ)

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

MCH
quelle