Funções aleatórias de baixo grau como um polinômio real

21

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 ?f:{0,1}n{0,1}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.dd2dnd2dd2dd2ddd

Portanto, a pergunta é: existe uma maneira de provar uma função booleana de baixo grau que evita esses dois problemas?

Igor Shinkar
fonte
3
Você deseja que a função real seja a restrição de um polinômio real de grau a 0-1 entradas ou deseja que f ( x ) = 1 iff p ( x ) > 0 para algum polinômio real p de grau no máximo d ? Ou alguma outra coisa? df(x)=1p(x)>0pd
Joshua Grochow
3
@ JoshuaGrochow Eu quero uma função cuja expansão de Fourier tenha o grau . Essa é a sua primeira opção. d
Igor Shinkar
11
Qual é o seu modelo? A anotação da função de amostra leva tempo, ou n O ( d ) se você deseja gerar a expansão de Fourier. D é uma constante fixa? 2nnO(d)d
MCH
3
Eu adicionei mais alguns detalhes na pergunta.
Igor Shinkar
11
@MCH Se uma função for do grau (com peso zero acima do nível d ), ela não poderá depender de mais do que d 2 d coordenadas. Este é um resultado devido a Nisan e Szegedy. Pense no caso especial de d = 1 . Nesse caso, sabemos que a função depende de (no máximo) 1 coordenada. ddd2dd=1
Igor Shinkar

Respostas:

11

Aqui está um algoritmo que supera as tentativas triviais.

O seguinte é um fato conhecido (Exercício 1.12 no livro de O'Donnell): Se f:{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)2d4dS|f^(S)|2d.

Isso sugere um método de amostragem -

  1. Escolha números inteiros aleatórios não negativos aS para todos os conjuntos S[n] de tamanho no máximo d , que somam 4d .
  2. Deixe- f(x)=SaS2dχS(x).
  3. Verifique se f é booleano. Se sim, retorne f . Senão, volte para 1 .

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/((nd)+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:aS0}|A|d2dfA2d2d

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 é .dO(nd)d4dnd2d2O(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 é ).d1/22n

Avishay Tal
fonte
Agradável! Na verdade, isso fornece um algoritmo no qual whp (wrt ) gera o número máximo possível de coordenadas das quais a função de baixo grau pode depender. Basta considerar que seja suficientemente grande, experimente muitas funções e, para cada função, conte o número de coordenadas influentes. Saída o máximo que você vê. n = 10 d 2 ddn=10d2d
Igor Shinkar 29/10