Construcciones mejores que al azar.

10

Estoy interesado en ejemplos de construcciones en la teoría de la complejidad que son mejores que las construcciones aleatorias.

El único ejemplo de tal construcción que conozco es en el campo de los códigos de corrección de errores. Los códigos de geometría algebraica son mejores en algún rango de parámetros que los códigos aleatorios.

Uno puede construir fácilmente tales ejemplos artificiales. Estoy interesado en ejemplos como los códigos de geometría algebraica, donde es fácil hacer una construcción aleatoria y no es obvio cómo hacerlo mejor.

reference-request big-list derandomization pr.probability Klim
fuente

77

Esta pregunta es terriblemente vaga. Por lo menos, indique de qué campo está hablando.

Dave Clarke

Agregué la etiqueta [big-list] y la marqué para llamar la atención del moderador, pidiéndoles que hagan de esta pregunta una wiki comunitaria.

Tsuyoshi Ito

44

Me gusta la pregunta, pero podríamos querer limitar el alcance de alguna manera. Está claro que cosas como grupos finitos, planos proyectivos, etc., si los parametrizas de la manera correcta (número de tripletas que violan la asociatividad, por ejemplo), tendrán parámetros mucho mejores que las construcciones aleatorias.

Peter Shor

Estoy de acuerdo en que la pregunta es vaga. No sé cómo limitar el alcance. Cualquier sugerencia es bienvenida. Mi interés es de los ejemplos interesantes. Por ejemplo, cuando durante mucho tiempo la construcción aleatoria fue la mejor y se necesitan ideas no triviales para vencerla.

Klim

@Dave, no estoy seguro si esto debe ser una etiqueta CW o [lista grande], si una pregunta es vaga, debemos pedirle al OP que la aclare, tenga en cuenta que CW es irreversible. En mi humilde opinión, una pregunta como esta se puede modificar de una manera que realmente debe ser una pregunta de la lista grande.

Kaveh

11

$\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ $D$ $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$ $o(1)$ $0$ $D$ $N\rightarrow \infty$

alpoge
fuente

10

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

Luca Trevisan
fuente

6

$n$ $n-1$

Peter Shor
fuente

5

En general, las construcciones aleatorias y las codiciosas alcanzan los mismos límites (p. Ej., Códigos de corrección de errores). Una vez escuché una charla de Lovasz donde dijo que las elecciones codiciosas y las elecciones aleatorias son esencialmente lo mismo. Por lo tanto, cualquier construcción que supere la construcción codiciosa debería proporcionar una respuesta a su pregunta. Como un ejemplo rápido, la construcción que logra la capacidad de gráficos de Sperner es de este tipo. Como dijo Peter Shor, realmente hay muchos ejemplos en combinatoria extrema.

Ugo
fuente

Construcciones mejores que al azar.

Respuestas: