Funciones aleatorias de bajo grado como un polinomio real

¿Hay una manera (razonable) de muestrear una función booleana uniformemente aleatoria cuyo grado como polinomio real es como máximo ? $f:\{0,1\}^n \to \{0,1\}$ $d$

EDITAR: Nisan y Szegedy han demostrado que una función de grado depende a lo sumo de las coordenadas , por lo que podemos suponer que . Los problemas que veo son los siguientes: 1) Por un lado, si elegimos una función booleana aleatoria en las coordenadas , entonces su grado será cercano a , mucho más alto que . 2) Por otro lado, si seleccionamos cada coeficiente de grado como máximo al azar, entonces la función no será booleana. $d$ $d2^d$ $n \leq d2^d$ $d2^d$ $d2^d$ $d$ $d$

Entonces la pregunta es: ¿hay alguna forma de probar una función booleana de bajo grado que evite estos dos problemas?

randomness boolean-functions bounded-degree Igor Shinkar
fuente

¿Desea que la función real sea la restricción de un polinomio real de grado a 0-1 entradas, o desea que sea iff para algún polinomio real de grado a lo sumo ? ¿O algo mas?

d

$d$

f (x) = 1

$f(x) = 1$

p (x) > 0

$p(x) > 0$

p

$p$

d

$d$

Joshua Grochow

@JoshuaGrochow Quiero una función cuya expansión de Fourier tenga grado . Esa es tu primera opción.

d

$d$

Igor Shinkar

Cual es tu modelo Anotar la función muestreada toma tiempo, o si desea generar la expansión de Fourier. ¿Es una constante fija?

2^{n}

$2^n$

n^{O (d)}

$n^{O(d)}$

d

$d$

MCH

Agregué algunos detalles más en la pregunta.

Igor Shinkar

@MCH Si una función es de grado

d

$d$ (con peso cero por encima del nivel

d

$d$ ), entonces no puede depender de más de

d 2^{d}

$d2^d$ coordenadas. Este es un resultado debido a Nisan y Szegedy. Piensa en el caso especial de

d = 1

$d=1$ . En este caso, sabemos que la función depende (como máximo) de 1 coordenada.

Igor Shinkar

Respuestas:

Aquí hay un algoritmo que supera los intentos triviales.

El siguiente es un hecho conocido (Ejercicio 1.12 en el libro de O'Donnell): Si $f:\{-1,1\}^n\to\{-1,1\}$ es una función booleana que tiene un grado $\le d$ como polinomio, entonces cada coeficiente de Fourier de $f$ , es un múltiplo entero de . Usando Cauchy-Schwarz y Parseval se obtiene que hay como máximo coeficientes de Fourier distintos de cero y $\hat{f}(S)$ $2^{-d}$ $4^d$ $\sum_{S}{|\hat{f}(S)|}\le 2^{d}$ .

Esto sugiere un método de muestreo:

Elija enteros no negativos aleatorios $a_S$ para todos los conjuntos $S\subseteq[n]$ de tamaño como máximo $d$ , que suman $\le 4^d$ .
Deje $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$ .
Verifique que $f$ sea booleana. Si es así, regrese $f$ . De lo contrario, regrese a $1$ .

Tenga en cuenta que por cada grado $\le d$ polinomio $f$ exactamente una elección de enteros aleatorios en el Paso 1 generará el polinomio $f$ . La probabilidad de obtener un grado específico $\le d$ polinomio es Por lo tanto, necesitamos repetir este proceso como máximo veces, con expectativa, antes de detenerlo.

1 / (\binom{(\binom{n}{\leq d}) + 4^{d}}{4^{d}}) = 1 / O (n / d)^{d 4^{d}} .

$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$

O (n / d)^{d 4^{d}}

$O(n/d)^{d4^d}$

Queda por mostrar cómo realizar el paso 3. Se puede definir . Compruebe que (que debe contener por Nisan-Szegedy para cada función booleana) y luego evaluar en todas las posibles asignaciones a las variables en . Esto se puede hacer a tiempo . Gur y Tamuz ofrecen un algoritmo aleatorio mucho más rápido para esta tarea, sin embargo, dado que esta parte no domina la complejidad del tiempo, es suficiente. $A = \bigcup\{S:a_S\neq 0\}$ $|A| \le d 2^d$ $f$ $A$ $2^{d 2^d}$

En general, el algoritmo produce una muestra aleatoria de un grado polinomio en el tiempo . Bajo el supuesto de que la complejidad del tiempo es . $\le d$ $O(\frac{n}{d})^{d4^d}$ $n \le d2^d$ $2^{O(d^2 4^d)}$

Este no es un algoritmo de muestreo de tiempo polinómico, aunque es mucho más rápido que muestrear una función completamente aleatoria (en cuyo caso la probabilidad de obtener un grado específico polinomio es 1/2 ). $\le d$ $1/2^{2^n}$

Avishay Tal
fuente

¡Agradable! En realidad, esto proporciona un algoritmo que whp (wrt ) genera el número máximo posible de coordenadas de las que puede depender la función de bajo grado. Simplemente tome para que sea lo suficientemente grande, muestree muchas funciones y, para cada función, cuente el número de coordenadas influyentes. Salida del máximo que ves.

d

$d$

n = 10 d 2^{d}

$n = 10d2^{d}$

Igor Shinkar