О сложности параллельных префиксных схем с ограниченным ветвлением

Доказано, что сложность универсальной префиксной схемы глубины $n$ на $2^n$ входах с ограничением $2$ на ветвление выходов элементов не меньше $0{,}75(n-1)2^{n}.$ Также приводится несколько простых конструкций и верхних оценок сложности префиксных схем с ветвлением $2$ и глубиной $n+k.$ Ил. 4, библиогр. 14.