Bessere Untergrenzen als 3n für nicht-boolesche Funktionen?

Blums -Untergrenze ist die bekannteste Schaltkreisuntergrenze über die gesamte Basis für eine explizite Funktion f : { 0 , 1 } n → { 0 , 1 } , vgl. Juknas Antwort auf diese Frage für verwandte Ergebnisse.$3n-o(n)$$f : \{0,1\}^n \to \{0,1\}$

Was sind die bekanntesten unteren Grenzen , wenn der Bereich von ist { 0 , 1 } m ? Erhalten wir insbesondere etwas Besseres für m = n oder für m = 2 ?$f$$\{0,1\}^m$$m = n$$m = 2$

Nach der Arbeit A Lower Bound auf der Schaltkreisgröße über U 2 einer linearen Booleschen Funktion$5n − o(n)$$U_2$ von Kulikov, Melanich und Mihajlin, wenn gibt es keine unteren Grenzen, die besser als 3 sind n - o ( n ) . Es wird auch ein Verfahren zum Erhalten von Funktionen beschrieben, für die eine untere Grenze von 4 n - o ( n ) gilt, wenn m = $m=o(n)$$3n - o(n)$$4n - o(n)$$m=n$, basierend auf einem Ergebnis von Lamagne und Savage.

hier sind neue Ergebnisse zu dieser , sagte der 1 sein ^st in ~ 3 Jahrzehnte und einige kurzen Kommentar

• Eine unter 3n liegende Grenze für die Schaltungskomplexität einer expliziten Funktion / Find, Golovnev, Hirsch, Kulikov

  Wir betrachten Boolesche Schaltungen über die gesamte Binärbasis. Wir beweisen ein $(3+\frac{1}{86})n−o(n)$$3n−o(n)$

• Besserer Kreislauf, niedrigere Grenzen für explizite Funktionen / Ilya Razenshteyn, MIT CSAIL-Studentenblog