Existe uma maneira (razoável) de amostrar uma função booleana aleatória uniformemente cujo grau como um polinômio real é no máximo d ?
EDIT: Nisan e Szegedy mostraram que uma função do grau depende de no máximo d 2 d coordenadas, portanto, podemos assumir que n ≤ d 2 d . Os problemas que vejo são os seguintes: 1) Por um lado, se escolher uma função booleana aleatória d 2 d coordenadas, então seu grau será perto d 2 d , muito maior do que d . 2) Por outro lado, se escolhermos cada coeficiente de grau no máximo d aleatoriamente, a função não será booleana.
Portanto, a pergunta é: existe uma maneira de provar uma função booleana de baixo grau que evita esses dois problemas?
randomness
boolean-functions
bounded-degree
Igor Shinkar
fonte
fonte
Respostas:
Aqui está um algoritmo que supera as tentativas triviais.
O seguinte é um fato conhecido (Exercício 1.12 no livro de O'Donnell): Sef:{−1,1}n→{−1,1} é uma função booleana que possui grau ≤d como polinômio, então todo coeficiente de Fourier de f , f ( S ) é um múltiplo inteiro de 2 - d . Usando Cauchy-Schwarz e Parseval, obtém-se que existem no máximo 4 d coeficientes de Fourier diferentes de zero e ∑ S | ˆf^(S) 2−d 4d ∑S|f^(S)|≤2d .
Isso sugere um método de amostragem -
Observe que, para cada grau≤d polinômio f exatamente uma escolha de números inteiros aleatórios na Etapa 1 gerará o polinômio f . A probabilidade de obter um grau específico ≤d polinômio é
Portanto, precisamos repetir esse processo no máximo vezes, na expectativa, antes de parar.1/((n≤d)+4d4d)=1/O(n/d)d4d. O(n/d)d4d
Resta mostrar como executar a etapa 3. Pode-se definir . Verifique se (que deve segurar por Nisan-Szegedy para cada função booleana) e depois avaliar em todas as atribuições possíveis para as variáveis . Isso pode ser feito no tempo . Gur e Tamuz oferecem um algoritmo aleatório muito mais rápido para esta tarefa, no entanto, como essa parte não domina a complexidade do tempo, isso é suficiente.A=⋃{S:aS≠0} |A|≤d2d f A 2d2d
No geral, o algoritmo produz uma amostra aleatória de um grau polinômio no tempo . Sob a suposição de que a complexidade do tempo é .≤d O(nd)d4d n≤d2d 2O(d24d)
Este não é um algoritmo de amostragem de tempo polinomial, embora seja muito mais rápido do que amostrar uma função completamente aleatória (nesse caso, a probabilidade de obter um grau específico polinômio é ).≤d 1/22n
fonte