Konstruktionen besser als eine zufällige.

Ich interessiere mich für Beispiele von Konstruktionen in der Komplexitätstheorie, die besser sind als zufällige Konstruktionen.

Das einzige mir bekannte Beispiel für eine solche Konstruktion ist das Gebiet der Fehlerkorrekturcodes. Algebraische Geometriecodes sind in einigen Parameterbereichen besser als zufällige Codes.

Man kann solche künstlichen Beispiele leicht konstruieren. Ich interessiere mich für Beispiele wie algebraische Geometriecodes, bei denen es einfach ist, eine zufällige Konstruktion zu erstellen, und es nicht offensichtlich ist, wie man es besser macht.

Ramanujan-Graphen haben den zweiten Eigenwert (mitDder Grad des Graphen), während zufällige Graphen nurλ2≤2$\lambda_2\leq \frac{2\sqrt{D-1}}{D}$$D$whp Tatsächlich haben wir im Allgemeinenλ2≥2$\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$, wobei dero(1)-TermbeikonstantemD(als Anzahl der EckpunkteN→∞)auf0geht, so dass diese in gewissem Sinne optimal sind.$\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$$o(1)$$0$$D$$N\rightarrow \infty$

$\{ 1,\ldots,N \}$$\{ 1,\ldots,N\}$$N^{0.9}$$N^{1-o(1)}$

$n$$n-1$

Im Allgemeinen erreichen zufällige Konstruktionen und gierige Konstruktionen die gleichen Grenzen (z. B. Fehlerkorrekturcodes). Einmal hörte ich einen Vortrag von Lovasz, in dem er sagte, dass gierige und zufällige Entscheidungen im Wesentlichen gleich sind. Jede Konstruktion, die die gierige Konstruktion übertrifft, sollte eine Antwort auf Ihre Frage geben. Ein Beispiel hierfür sind Konstruktionen, die die Sperner-Kapazität von Graphen erreichen. Wie Peter Shor sagte, gibt es wirklich viele Beispiele in der extremen Kombinatorik.