Enganando funções simétricas arbitrárias

17

A distribuição D é dito ϵ -fool uma função se . E é dito que engana uma classe de funções se ela engana todas as funções nessa classe. Sabe-se que os espaços tendenciosos enganam a classe de paridades sobre subconjuntos. (veja Alon-Goldreich-Hastad-Peralta para algumas construções legais de tais espaços). A pergunta que quero fazer é uma generalização disso para funções simétricas arbitrárias.| E x U ( f ( x ) ) - E x D ( f ( x ) ) | ϵ ϵf|ExU(f(x))ExD(f(x))|ϵ

ϵ

Pergunta: Suponha que tomemos a classe de funções simétricas arbitrárias sobre algum subconjunto, temos distribuição (com pequeno suporte) que engana essa classe?

Algumas pequenas observações:

  • É suficiente enganar os limites exatos ( EThkS(x) é 1 se e somente se x tiver exatamente k uns entre os índices em S ). Qualquer distribuição que ϵ -fools estes limites exatos irá enganar todas as funções simétricas ao longo pedaços. (Isso ocorre porque todas as funções simétricas podem ser escritas como uma combinação linear real desses limites exatos, em que os coeficientes na combinação são 0 ou 1. A linearidade da expectativa nos dá o que queremos). Um argumento semelhante também funciona para limites gerais ( é 1 se e somente sen Th S k ( x ) xnϵn

    ThkS(x)xtem pelo menos ones entre os índices em )SkS

  • Existe uma construção explícita de uma distribuição com suporte via PRG do Nisan para LOGSPACE .nO(logn)

  • Os espaços arbitrários - não funcionarão. Por exemplo, se é o conjunto de todos os modo que o número de unidades em x seja um mod 3 diferente de zero, isso é realmente enviesado para muito pequeno (de um resultado de Arkadev Chattopadyay ). Mas claramente isso não engana a função MOD3.S x ϵ ϵϵSxϵϵ

Um subproblema interessante pode ser o seguinte: suponha que apenas queremos enganar funções simétricas sobre todos os n índices , temos um espaço agradável? Pelas observações acima, precisamos apenas enganar as funções de limite sobre bits, que é apenas uma família de funções. Assim, pode-se simplesmente escolher a distribuição por força bruta. Mas existem exemplos mais agradáveis ​​de espaços que enganam 'para cada ?n + 1 mil [ n ] k knn+1Thk[n]k

Ramprasad
fonte
Talvez este comentário possa ajudar. A conjectura de Linial e Nisan foi resolvida recentemente por Mark Braverman. O título do artigo é "Independência polilogarítmica engana os circuitos AC ^ 0". cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf
Mirmojtaba Gharibi

Respostas:

11

Sim, uma solução geral para esse problema foi recentemente fornecida por Parikshit Gopalan, Raghu Meka, Omer Reingold e David Zuckerman, consulte Geradores pseudoaleatórios para formas combinatórias .

Esse documento trata de uma configuração ainda mais geral, na qual o gerador gera blocos log m- bits, que são alimentados por funções booleanas arbitrárias, cujas n saídas são alimentadas por uma função simétrica booleana.n logmn

Uma variedade de sub-casos já era conhecida; veja, por exemplo, Geradores de bits pseudo - aleatórios que enganam somas modulares , Independência limitada enganam meios-espaços e Geradores pseudo - aleatórios para funções de limite polinomial . O primeiro trata de somas modulo . O segundo e o terceiro lidam com precisão com os testes de limite mencionados, no entanto, o erro não é bom o suficiente para aplicar seu raciocínio para obter um resultado para todas as funções simétricas.p

Manu
fonte
11
Mas Gopalan-Meka-Reingold-Zuckerman não fornece um PRG ideal para erro polinomial inverso, certo? Para uma constante , é ideal. No entanto, muito obrigado pelo ponteiro. ε
Ramprasad
Na verdade eles não. Em geral, esse é um objetivo difícil, e há relativamente poucos exemplos na literatura em que uma dependência logarítmica de é alcançada. ϵ
Manu