Platzsparende „industrielle“ unsymmetrische Expander

Ich suche unsymmetrische Expander, die "gut" und "platzsparend" sind. Insbesondere ist ein zweigliedriger linksregelmäßiger Graph , | A | = n , | B | = m , mit dem linken Grad d ist ein ( k , ϵ ) -Expander, wenn für jedes S ⊂ A der Größe höchstens k die Anzahl der verschiedenen Nachbarn von S in B mindestens ( 1 $G=(A,B,E)$$|A|=n$$|B|=m$$d$$(k,\epsilon)$$S \subset A$$k$$S$$B$. Es ist bekannt, dass die probabilistische Methode einen solchen Graphen mit d = O ( log ( n / k ) / ϵ ) und m = O ( k log ( n / k ) / ϵ 2 ) liefert. Man braucht jedoch O ( n d $(1-\epsilon)d|S|$$d=O(\log (n/k)/\epsilon)$$m=O(k \log(n/k)/\epsilon^2)$$O(n d)$Platz zum Speichern eines solchen Graphen. Außerdem muss man auch auf diesen Speicher zugreifen, wenn man etwas mit dem Graphen macht, was ebenfalls Kosten verursachen kann. Idealerweise möchte man eine explizite Konstruktion. Bekannte Konstruktionen erreichen jedoch meines Wissens (zumindest nachweislich) noch etwas weiter entfernte Parameter.

Meine Frage: Gibt es andere, möglicherweise nicht explizite Konstruktionen, die Grenzen "näher" an den oben genannten erreichen und dennoch "deutlich weniger" als verwenden?$O(nd)$

Ich suche nach Antworten in einer dieser drei Kategorien: (a) Theoreme (b) Vermutungen (c) Beobachtungen und "Kriegsgeschichten" wie "Wir haben dies getan und es schien irgendwie zu funktionieren". Dh "industrielle" Expander sind in Ordnung. Ich bevorzuge (a) gegenüber (b) und (b) gegenüber (c), aber Bettler können keine Wahl sein :)

Hier ist ein Beispiel für eine Konstruktion vom Typ (c). Nehmen Sie zufällige lineare Hash-Funktionen h i : [ n ] → [ m ] (mod m ) und verbinden Sie jeden Vertex i mit h 1 ( i ) … h d ( i ) . Ich und mein Schüler machten einige Experimente und es schien "gut" zu funktionieren. Gibt es Theoreme oder Vermutungen über diese oder verwandte Konstruktionen?$d$$h_i: [n] \to [m]$$m$$i$$h_1(i) \ldots h_d(i)$

Vielen Dank!

$d$$h_1,\dots,h_d$$v$$h_1(v),\dots,h_d(v)$$(k,\epsilon)$$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$

Ich dachte, dass ein Blick auf Umfragen / Vorträge von Avi Wigderson bei Ihrer Frage hilfreich sein könnte. Hier sind Folien aus einem Vortrag: Expander Tutorial, Juni 2010 . Der Aufbau beginnt auf Seite 40.

In Bezug auf die Platzkomplexität halte ich es für hilfreich, wenn Sie die Operationen angeben, die Sie an der Grafik ausführen müssen. Wenn ich mich nicht irre, erlauben einige Konstruktionen Operationen wie das Berechnen der Nachbarschaft im Logspace.