Классы сложности линейных цепей

Класс $\textrm{NC}^i$ является классом функций, вычисляемых семействами схем ограниченного вкручивания, размера $n^{O(1)}$ и глубины $O(\log^i(n))$ . $\textrm{NC}$ -hierarchy является объединением этих классов.

Есть ли какое-либо исследование линейного размера этой иерархии? То есть схемы семейств ограниченного разветвления, глубины полилога и линейного размера?

Я знаю, что существует некоторая работа с линейным $\textrm{AC}^0$ но больше ничего. Заметим, что, по крайней мере, линейный $\textrm{NC}^1$ нетривиален, поскольку он содержит регулярные языки (и, следовательно, некоторые $\textrm{NC}^1$ -комплектные языки).

Из работы Valiant [1, 2] следует, что линейный размер $\textrm{NC}^1$ может быть смоделирован цепями размером $2^{O(n / \log \log n)}$ с глубиной три и неограниченным разветвлением.

Хорошее изложение этого результата см. В разделе 3 обзора Виолы [3].

[1] Лесли Г. Валиант. Теоретико-графические аргументы в низкоуровневой сложности . В кн .: Математические основы информатики 1977. MFCS 1977. Конспект лекций по информатике, том 53. Springer, Berlin, Heidelberg.

[2] Лесли Г. Валиант. Экспоненциальные нижние оценки для ограниченных монотонных цепей . В кн .: Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '83). ACM, Нью-Йорк, Нью-Йорк, США, 110-117.

[3] Эмануэле Виола. На мощности вычислений малой глубины . Основы и направления теоретической информатики, вып. 5, число 1, стр. 1--72, 2009.