Meilleures limites inférieures à 3n pour les fonctions non booléennes?

La borne inférieure Blum est la borne inférieure du circuit la plus connue sur la base complète d'une fonction explicite , cf. Réponse de Jukna à cette question pour des résultats connexes.f : { 0 , 1 } n → { 0 , 1 $3n-o(n)$$f : \{0,1\}^n \to \{0,1\}$

Quelles sont les bornes inférieures les plus connues si la plage de est ? En particulier, obtenons-nous quelque chose de mieux pour ou pour ?{ 0 , 1 } m m = n m = $f$$\{0,1\}^m$$m = n$$m = 2$

Selon l'article A borne inférieure sur la taille du circuit sur U_2 d'une fonction booléenne linéaire$5n − o(n)$$U_2$ par Kulikov, Melanich et Mihajlin, lorsque $m=o(n)$ il n'y a pas de bornes inférieures connues mieux que $3n - o(n)$ . Il décrit également une méthode pour obtenir des fonctions pour lesquelles une limite inférieure de $4n - o(n)$ tient, lorsque $m=n$ , basée sur un résultat de Lamagne et Savage.

voici de nouveaux résultats sur ce qui serait la 1 ^ère en ~ 3 décennies et quelques brefs commentaires

• Une borne inférieure meilleure que 3n pour la complexité du circuit d'une fonction explicite / Find, Golovnev, Hirsch, Kulikov

  Nous considérons les circuits booléens sur la base binaire complète. Nous prouvons une borne inférieure sur la taille d'un tel circuit pour un prédicat explicitement défini, à savoir un disperseur affine pour la dimension sublinéaire. Cela améliore la limite de Norbert Blum (1984).$(3+\frac{1}{86})n−o(n)$$3n−o(n)$

• Better Circuit Lower Bounds for Explicit Functions / Ilya Razenshteyn, MIT CSAIL student blog