Limites inferiores a 3n melhores para funções não booleanas?

O limite inferior Blum é limite inferior do circuito mais conhecido em toda a base para uma função explícita , cf. A resposta de Jukna a esta pergunta para resultados relacionados.$3n-o(n)$$f : \{0,1\}^n \to \{0,1\}$

Quais são os limites inferiores mais conhecidos se o intervalo de for ? Em particular, obtemos algo melhor para ou ?$f$$\{0,1\}^m$$m = n$$m = 2$

De acordo com o artigo A Limite inferior no tamanho do circuito acima de de uma função booleana linear$5n − o(n)$$U_2$ de Kulikov, Melanich e Mihajlin, quando não há limites inferiores conhecidos melhor que . Ele também descreve um método para obter funções para as quais um limite inferior de mantém, quando , com base no resultado de Lamagne e Savage.$m=o(n)$$3n - o(n)$$4n - o(n)$$m=n$

aqui estão os novos resultados nesta dito ser o 1 ^st em ~ 3 décadas e alguns breve comentário

• Um limite inferior a 3n para a complexidade do circuito de uma função explícita / Find, Golovnev, Hirsch, Kulikov

  Consideramos circuitos booleanos em toda a base binária. Nós provamos um limite inferior no tamanho de um circuito para um predicado definido explicitamente, a saber, um dispersor afim para dimensão sublinear. Isso melhora o$(3+\frac{1}{86})n−o(n)$$3n−o(n)$ limite de de Norbert Blum (1984).

• Melhores limites inferiores do circuito para funções explícitas / Ilya Razenshteyn, blog do aluno do MIT CSAIL