Referências sobre limites inferiores do circuito

Preâmbulo

Os sistemas interativos de prova e os protocolos Arthur-Merlin foram introduzidos por Goldwasser, Micali e Rackoff e Babai em 1985. No início, pensava-se que o primeiro era mais poderoso que o segundo, mas Goldwasser e Sipser mostraram que tinham o mesmo poder ( em relação ao reconhecimento de idiomas). Portanto, neste post, usarei os dois conceitos de forma intercambiável.

Seja a classe de idiomas que admite um sistema interativo de provas com rodadas. BABAI provou que . (Um resultado relativizável.)$IP[k]$I P [ S ( 1 ) ] ⊆ ¸ P $k$$IP[O(1)] \subseteq \Pi_2^P$

A princípio, não se sabia se o número ilimitado de rodadas pode aumentar o poder do IP. Em particular, foi demonstrado ter relativizações contraditórias: Fortnow e Sipser mostrou que para alguns a Oracle , é válido que . (Portanto, em relação a A , IP [poli] não é uma superclasse de PH ).)$A$$coNP^A \not\subset IP[poly]^A$$A$$IP[poly]$$PH$

Por outro lado, o seguinte artigo:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

mostra que, por algum oráculo $B$ , temos $IP[poly]^B \not\subset PH^B$ . (Portanto, $IP[poly]^B \neq IP[O(1)]^B$ pois, como afirmado acima, o último é uma subclasse de $\Pi_2^{P,B}$ .)

A questão

O artigo de Aiello, Goldwaseer e Hastad (citado acima) afirma:

As técnicas empregadas são extensões das técnicas para provar limites inferiores em circuitos de pequena profundidade usados ​​em [FSS], [Y] e [H1].

onde [FSS], [Y] e [H1] são:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

Achei os papéis muito antigos e extremamente difíceis de acompanhar. Li o capítulo 14 do livro de Arora & Barak , mas aparentemente ele não cobre tudo o que preciso.

Que referências em "Limites inferiores do circuito" você sugere?

(Preciso especialmente de referências de pesquisa; as que são mais recentes e que não precisam de muita experiência são mais preferíveis.)

O que você deseja é uma boa referência para entender os limites inferiores exponenciais para os circuitos calculam a função PARITY.$AC^0$

Agora você não declarou se realmente deseja entender a prova ou apenas entender as coisas em alto nível, da maneira como um artigo de pesquisa explicaria as coisas.

Um artigo de pesquisa que li e gostei recentemente é " A complexidade das funções finitas " de Boppana e Sipser.

Se você realmente quer se sentar e entender a prova, pode ler as provas com base no lema da troca (que aparece nos artigos que você citou - [FSS], [Y] e [H1]) ou no Razborov-Smolensky prova.

Para provas usando o Switching Lemma, o Ph.D. de Håstad tese é uma boa leitura, se um pouco difícil de seguir, se você é novo na área. Uma melhor exposição da prova está em "Introdução à complexidade do circuito e um guia para a prova de Håstad", de Allan Heydon. O único problema é que não consigo encontrá-lo online e tenho uma cópia impressa. Eu realmente recomendo se você é novo no circuito de complexidade.

Para a abordagem Razborov-Smolensky, basta pesquisar no Google e você obterá um monte de notas de aula. Entendi o limite inferior dessas três notas de aula: Sanjeev Arora , Madhu Sudan e Kristoer Arnsfelt Hansen .

Se você acha difícil acompanhar a exposição do Switching Lemma na tese de Hastad, pode tentar `` A Switching Lemma Primer '' de Paul Beame , que tem uma versão diferente devido a Razborov (que também usa explicitamente árvores de decisão, algo que é crucial em algumas aplicações do lema de comutação)

Este livro é ótimo para explicar os limites inferiores, se você tiver acesso a ele.

Introdução à complexidade do circuito por Heribert Vollmer.

Acabei de ler e, embora diga "introdução", é um tratamento muito profundo da complexidade do circuito. Explica com detalhes todas as técnicas (mais populares) para provar os limites inferiores do circuito no capítulo 3.

Uma referência mais recente seria Complexidade da Função Booleana por Stasys Jukna. Você só precisa enviar um e-mail para ele ou preencher o formulário para obter o pdf do rascunho.

Uma referência mais antiga, mas ainda agradável, é a pesquisa A complexidade das funções finitas de Boppana e Sipser. Esta pesquisa é muito legível em comparação com outras fontes.

Outra boa referência é o livro Funções booleanas e modelos de computação de Clote e Kranakis.

Não sou especialista, mas provavelmente há informações interessantes no livro azul ( http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ ).

Há também um artigo de Allender em 1997: Complexidade do circuito antes do alvorecer do novo milênio

Emanuele Viola publicou o livro " Sobre o poder da computação em pequena profundidade ", que inclui muitos resultados nos limites inferiores do circuito.

Uma versão preliminar do livro pode ser encontrada aqui .