Paridade e

19

Paridade e são como gêmeos inseparáveis. Ou assim parece nos últimos 30 anos. À luz do resultado de Ryan, haverá um interesse renovado nas turmas pequenas. $AC^0$

Furst Saxe Sipser de Yao a Hastad são todas paridade e restrições aleatórias. Razborov / Smolensky é um polinômio aproximado com paridade (ok, mod gates). Aspnes et al. Usam grau fraco na paridade. Além disso, Allender Hertrampf e Beigel Tarui tratam do Toda em turmas pequenas. E Razborov / Beame com árvores de decisão. Tudo isso cai na cesta de paridades.

1) Quais são os outros problemas naturais (além da paridade) que podem ser mostrados diretamente como não estando em ? $AC^0$

2) Alguém conhece uma abordagem drasticamente diferente do limite inferior em AC ^ 0 que foi tentada?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
fonte

13

O resultado de Benjamin Rossman no limite inferior para k-clique do STOC 2008. $AC^0$

Referências:

Paul Beame, " A Switching Lemma Primer ", Relatório Técnico 1994.
Benjamin Rossman, " Sobre a complexidade em profundidade constante do k-Clique ", STOC 2008.

Kaveh
fonte

Rossman não é incluído na cartilha de Beame, que também tinha camarilha? Os argumentos são mais intrincados, é claro.

V Vinay

@V Vinay: você pode dar um link para o artigo de Paul Beame?

Kaveh

4

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

@ Srikanth, pensei que V Vinay está dizendo que Beame tem um resultado mais novo, mas não consegui encontrar nenhum em sua página. Obrigado pela clarificação.

Kaveh

11

Srikanth está certo sobre os limites. Kaveh, não é um artigo novo; Eu usei "subsumed" no sentido de ter listado Beame na minha pergunta e, portanto, estava ciente do limite inferior da camarilha.

V Vinay

12

Existe a abordagem "de cima para baixo" de Håstad, Jukna e Pudlák, como foi feito em seu artigo Limites inferiores de cima para baixo para circuitos de profundidade três . Infelizmente, até agora não conseguimos estender a abordagem para profundidades mais altas.

Kristoffer Arnsfelt Hansen
fonte

Sim. Eu pensei que você tivesse um artigo influenciado por essa abordagem?

V Vinay

10

$AC^{0}$

2) Uma abordagem topológica, novamente trabalhando apenas para circuitos de profundidade três, foi proposta por Kriegel e Waack .

Alessandro Cosentino
fonte

2

Maioria é a mesma coisa realmente. Eu deveria ter mencionado isso. Além disso, houve um artigo de Boppana sobre a maioria em meados dos anos 80.

precisa

8

Os outros dois métodos "clássicos" são o método de gargalo de Haken e o método de fusão de Karchmer (assim chamado por Avi Wigderson), ambos muito mais fáceis de aplicar em ambientes monótonos.

Yuval Filmus
fonte

Paridade e

Respostas: