Matriz balanceada explícita

20

¿Es posible construir una explícita 0 / 1 -matrix con N 1,5 queridos tal que cada N 0.499 × N 0,499 submatriz contiene menos de N 0,501 queridos?N×N 0/1N1.5N0.499×N0.499N0.501

O probablemente sea posible construir un conjunto de golpes explícito para dicha propiedad.

Es fácil ver que la matriz aleatoria tiene esta propiedad con probabilidad exponencialmente cercana a . Además, el lema de mezcla del expansor no es suficiente para derivar esta propiedad.1

Supongo que los generadores pseudoaleatorios que engañan a los rectángulos combinatorios podrían ayudar aquí, pero están diseñados para distribuciones uniformes y básicamente necesito aquí.B(N2,N0.5)

ilyaraz
fuente
55
Es una pregunta interesante: tengo curiosidad por la motivación.
Suresh Venkat
@Suresh Proviene de la no extracción cuantitativa de información mutua. Si te interesa, puedo dar más detalles.
ilyaraz
De hecho lo soy. puede enviarme un correo electrónico ([email protected]) si es más fácil de esa manera.
Suresh Venkat

Respuestas:

11

Lo que está buscando es un extractor de un bit para dos fuentes independientes: una función , de modo que, siempre que X, Y sean variables aleatorias con entropía mínima 0.499 * log (N), E (X, Y) está casi equilibrado.E:[N]×[N]{0,1}

Es un problema difícil notorio. Para los parámetros que desea, creo que fue resuelto por Bourgain. Ver aquí: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Dana Moshkovitz
fuente
1
Bourgain da un sesgo para algunos α > 0 . No estoy seguro de que el análisis puede dar α = 1 / 2 . Si yo fuera tú, lo estudiaría y comprobaría. También puede preguntarle a Anup Rao, Zeev Dvir, Avi Wigderson o cualquiera de las otras personas que trabajaron en este problema. p=Nαα>0α=1/2
Dana Moshkovitz
77
@ilyaraz: Cuando tú (o alguien) descubra si la construcción de Bourgain da una matriz deseada o no, ¡comparte (a menos que te importe)!
Tsuyoshi Ito
1
Este ha sido un Q&A muy interesante. Secundaré la solicitud de Tsuyoshi.
Suresh Venkat
2
Al releer la pregunta y la respuesta (hace un tiempo ...), creo que no me di cuenta de que el interlocutor solo quería N ^ {1.5}, lo que corresponde a extraer un bit que es 1 con probabilidad N ^ {-0.5} en lugar de un bit equilibrado. Aún así, creo que la referencia a extractores de dos fuentes es útil. Me imagino que técnicas similares serían útiles para la configuración de la pregunta.
Dana Moshkovitz
1
1) Si un extractor genera k bits casi uniformes, entonces, en particular, puede obtener un bit que es 1 con probabilidad ~ 1/2 ^ k. 2) Esto es bastante derrochador, y me parece una buena pregunta de investigación para encontrar una manera más eficiente de generar tales bits.
Dana Moshkovitz
2

Esta respuesta se basa en la idea de Dana en su respuesta anterior.

Creo que puede construir una matriz de este tipo utilizando condensadores con pérdida de dos fuentes. Arregle y diga N = 2 n . Suponga que tiene una función explícita f ( x , y ) que toma cualquier dos fuentes independientes aleatorios ( X , Y ) , cada uno de longitud n y que tienen min-entropía al menos k = n ( 1 / 2 - δ ) y emite una secuencia de de n = n / 2δ=0.001N=2nf(x,y)(X,Y)nk=n(1/2δ)n=n/2bits que se -cerca de una distribución con min-entropía al menos k ' = n ( 1 / 2 - 3 δ ) . Creo que puede usar argumentos probabilísticos estándar para mostrar que una función aleatoria satisface estas propiedades (con una probabilidad abrumadora) si 2 k > k + log ( 1 / ϵ ) + O ( 1 ) . El argumento probabilístico debe ser similar al utilizado en el siguiente documento para condensadores sin pérdidas y conductores más generales:ϵk=n(1/23δ)2k>k+log(1/ϵ)+O(1)

M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson. Aleatoriedad de conductores y expansión de grado constante más allá del grado / 2 barrera

En nuestro caso, establecemos , por lo que estamos seguros de la existencia de la función que necesitamos. Ahora, un argumento promedio muestra que hay una cadena z de n bits tal que el número de ( x , y ) con f ( x , y ) = z es al menos 2 1.5 n . Supongamos que conoce tal z y lo arregla (puede elegir cualquier z arbitrariaϵ=2knz(x,y)f(x,y)=z21.5nzzsi además sabe que su función asigna la distribución completamente uniforme a una distribución que es -cierre a uniforme). Ahora identifique las entradas de su matriz N × N por las posibilidades de ( x , y ) y ponga un 1 en la posición ( x , y ) iff f ( x , y ) = z . Por nuestra elección de z , esta matriz tiene al menos 2 1.5 nO(2n/2)N×N(x,y)1(x,y)f(x,y)=zz21.5n unos.

Ahora tome cualquier submatriz de y deje que X , Y sean distribuciones uniformes en las filas y columnas seleccionadas, respectivamente. Por la elección de f , sabemos que f ( X , Y ) está ϵ cerca de tener una entropía mínima k . Por lo tanto, si elegimos una entrada aleatoria uniforme de la submatriz, la probabilidad de tener un 1 es como máximo 2 - k + ϵ 2 - k + 12k×2kX,Yff(X,Y)ϵk12k+ϵ2k+1. Esto significa que tiene como máximo en la submatriz, según lo desee.22kk+1=O(2n/2+δ)

Por supuesto, llegar a una f explícita con los parámetros deseados (en particular, una longitud de salida casi óptima) es una tarea muy desafiante y no se conoce tal función hasta ahora.f

MCH
fuente