Лучше нижние оценки, чем 3n для небулевых функций?

Нижняя граница Блума $3n-o(n)$ - это лучшая известная нижняя граница схемы по полному базису для явной функции $f : \{0,1\}^n \to \{0,1\}$ , ср. Юкна ответ на этот вопрос для связанных результатов.

Каковы наиболее известные нижние оценки, если диапазон $f$ равен $\{0,1\}^m$ ? В частности, получаем ли мы что-нибудь лучше для $m = n$ или для $m = 2$ ?

Согласно статье A Нижняя граница для размера цепи по линейной булевой функции$5n − o(n)$$U_2$ Куликова, Меланича и Михайлина, когда , нет нижних границ, известных лучше, чем . Он также описывает метод получения функций, для которых выполняется нижняя оценка , когда , на основе результата Ламаня и Сэвиджа.$m=o(n)$$3n - o(n)$$4n - o(n)$$m=n$

Вот новые результаты, которые, как говорят, были ^{первыми} за 3 десятилетия, и некоторые краткие комментарии.

• Нижняя оценка лучше чем 3n для сложности схемы явной функции / Find, Golovnev, Hirsch, Kulikov

  Мы рассматриваем булевы схемы на полном двоичном базисе. Мы докажем нижнюю границу размера такой схемы для явно определенного предиката, а именно аффинного дисперсера для сублинейной размерности. Это улучшает границу Норберта Блума (1984).$(3+\frac{1}{86})n−o(n)$$3n−o(n)$

• Лучшая схема Нижние границы для явных функций / Илья Разенштейн, студенческий блог MIT CSAIL