Grau aproximado de

EDIT (v2): Adicionada uma seção no final sobre o que eu sei sobre o problema.

EDIT (v3): adicionada discussão sobre o grau do limiar no final.

Questão

Esta pergunta é principalmente uma solicitação de referência. Eu não sei muito sobre o problema. Quero saber se já houve trabalho anterior sobre esse problema. Em caso afirmativo, alguém pode me apontar para algum artigo que fale sobre esse problema? Eu também gostaria de conhecer os melhores limites atuais no grau aproximado de . Qualquer outra informação também seria apreciada (por exemplo, informações históricas, motivação, relação com outros problemas, etc.).$\textrm{AC}^0$

Definições

Seja uma função booleana. Seja um polinômio sobre as variáveis a com coeficientes reais. O grau de um polinômio é o grau máximo em todos os monômios. O grau de um monômio é a soma dos expoentes dos vários que aparecem nesse monômio. Por exemplo .$f:\{0,1\}^n \to \{0,1\}$$p$$x_1$$x_n$$x_i$$\textrm{deg}(x_1^7x_3^2) = 9$

Diz-se que um polinômio é aproximado se para todo . O grau aproximado de de uma função booleana , denotada como , é o grau mínimo de um polinômio que aproxima de . Para um conjunto de funções, , é o grau mínimo modo que todas as funções em possam ser aproximadas por um polinômio de grau no máximo d$p$$\epsilon$$f$$|f(x)-p(x)|<\epsilon$$x$$\epsilon$$f$$\widetilde{\textrm{deg}}_{\epsilon}(f)$$\epsilon$$f$$F$$\widetilde{\textrm{deg}}_{\epsilon}(F)$$d$$F$$\epsilon$$d$.

Observe que todas as funções podem ser representadas sem erro por um grau $n$ polinomial. Algumas funções realmente precisam de um polinômio de grau $n$ para se aproximar de qualquer erro constante. Paridade é um exemplo dessa função.

Declaração do problema

O que é $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$ ? (A constante 1/3 é arbitrária.)

Notas

Encontrei esse problema no artigo A complexidade quântica de consultas do AC0 de Paul Beame e Widad Machmouchi. Eles dizem

Além disso, nossos resultados não fazem nada para fechar a lacuna no limite inferior no grau aproximado de funções AC0.

Eles mencionam "o problema do grau aproximado de AC0" em seus agradecimentos também.

Então, eu suponho que já houve algum trabalho sobre esse problema antes? Alguém pode me indicar um artigo que fale sobre o problema? E quais são os limites superior e inferior mais conhecidos?

O que eu sei sobre o problema (Esta seção foi adicionada na v2 da pergunta)

O limite superior mais conhecido em que é conhecido é o limite superior trivial . O melhor limite inferior que conheço vem do limite inferior de Aaronson e Shi para os problemas de colisão e distinção de elementos, o que fornece um limite inferior de . (Para versões severamente restritas de , como fórmulas com tamanho de fórmula ou circuitos de profundidade 2 com portas , podemos provar um limite superior usando a complexidade da consulta quântica.)n ~ Ω (n2/3)AC0O(n2)o(n2)o(n$\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$$n$$\tilde{\Omega}(n^{2/3})$$\textrm{AC}^0$$o(n^2)$$o(n^2)$$o(n)$

Relacionado: grau limite (adicionado na v3)

Como Tsuyoshi aponta nos comentários, esse problema está relacionado ao problema de determinar o grau de limiar de . O grau de limiar de uma função é o grau mínimo de um polinómio tal que e . fpf(x)=$\textrm{AC}^0$$f$$p$f ( x ) = $f(x)=1 \implies p(x)>0$$f(x)=0 \implies p(x)<0$

Os limites inferiores para o grau limite de foram aprimorados por Sherstov. Ele exibe uma família de fórmulas de leitura única de profundidade constante em variáveis ​​cujo grau de limiar se aproxima de medida que a profundidade vai para o infinito, o que é quase restrito, pois as fórmulas de leitura única possuem limiar (e até aproximado ) grau . Veja http://eccc.hpi-web.de/report/2014/009/ . (Jan, 2014) nΩ($\mathrm{AC}^0$$n$O($\Omega(\sqrt{n})$$O(\sqrt{n})$

Um artigo de Mark Bun e Justin Thaler foi publicado recentemente no ECCC (meados de março de 2017), que responde precisamente a esta pergunta: "Um limite inferior quase ideal no grau aproximado de AC0"

Eles afirmam que para qualquer , existe uma função em tal que , quase fechando a lacuna com o limite superior trivial de . Eles conseguem isso com um método geral para aumentar o grau aproximado de uma função com grau aproximado sublinear, mantendo o número de variáveis ​​quase-lineares. Do resumo:f Um C 0 ~ d e g 1 / 3 ( f ) = Ω ( N 1 - δ ) S ( n $\delta > 0$$f$$\mathrm{AC}^0$$\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$$O(n)$

Especificamente, mostramos como transformar qualquer função booleana com grau aproximado em uma função em variáveis com grau aproximado pelo menos . Em particular, se , então é polinomialmente maior que . Além disso, se é calculado por um Booleano circuito de tamanho polinomial de profundidade constante, então é assim .d M O ( N ⋅ p o l y L o g ( n ) ) D = Ω ( n 1 / 3 · d 2 / 3 ) d = N 1 - Ω ( 1 ) D d f $f$$d$$F$$O(n \cdot \mathrm{polylog}(n))$$D = Ω(n^{1/3} · d^{2/3} )$$d = n^{1−Ω(1)}$$D$$d$$f$$F$

Essa é a atualização mais recente na extremidade inferior deste problema, e é um avanço significativo. As seções Introdução e Aplicação do documento também são boas fontes de referências para trabalhos anteriores e problemas relacionados.

Isenção de responsabilidade: ainda não li o artigo com atenção.