Limites Inferiores de Circuitos em Média Forte a partir de Derandomização Não Trivial

Em uma recente descoberta, C. Murray e R. R. Williams, STOC 2018, ACM, Nova Iorque, 2018, pp. 890--901, provaram que NQP = NTIMEn^{polylog (n)} não pode ser computado por circuitos ACC⁰ de tamanho polinomial (circuitos de profundidade constante consistindo em portas AND/OR/MODₘ para uma constante fixa m, uma classe fronteira em complexidade de circuitos). Isso foi recentemente fortalecido por L. Chen, FOCS 2019, IEEE, Piscataway, NJ, 2019, pp. 1281--1304, mostrando que NQP não pode ser (1/2+1/polylog (n))-aproximado por circuitos ACC⁰ de tamanho polinomial. Neste trabalho, provaremos que NQP não pode ser (1/2+1/n^{(1)})-aproximado por circuitos ACC⁰ de tamanho polinomial. Como uma aplicação direta, obtemos um gerador pseudorrandômico não determinístico infinitamente frequente para circuitos ACC⁰ de tamanho polinomial com comprimento de semente subpolinomial. Mais geralmente, estabelecemos uma conexão mostrando que, para uma classe típica de circuitos C, algoritmos determinísticos não triviais que estimam a probabilidade de aceitação de circuitos C implicam fortes limites inferiores de média (1/2 + 1/n^{(1)}) contra circuitos C. Também aplicamos esta conexão para provar novos limites inferiores contra várias subclasses de circuitos TC⁰ (circuitos de profundidade constante consistindo inteiramente de portas de maioria) e mostramos que a derandomização não trivial de MAJ MAJ implicaria limites inferiores no pior caso para TC⁰₃ (MAJ MAJ MAJ), sugerindo que os limites inferiores de TC⁰₃ provavelmente estão ao nosso alcance. Nossos dois novos ingredientes técnicos importantes são (1) técnicas de criptografia em NC⁰ B. Applebaum, Y. Ishai e E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888, e (2) provas verificáveis probabilísticas de proximidade com provas computáveis em NC¹.