Нижние оценки для формул постоянной глубины?

Мы много знаем об ограничениях (полиномиального размера) контуров постоянной глубины. Поскольку формулы с постоянной глубиной (полиномиального размера) представляют собой еще более ограниченную модель вычислений, все известные проблемы, которых нет в AC ⁰ , также не могут быть вычислены с помощью формулы постоянной глубины. Тем не менее, поскольку это более простая модель, я предполагаю, что есть еще проблемы, о которых известно, что они не вычислимы в этой модели. Это было изучено? (Я предполагаю, что это было, но я, вероятно, не использую правильные условия поиска.)

В частности, меня интересует следующий вопрос: существует ли какая-то функция f, которая может быть вычислена с помощью схемы AC ⁰ размера S, но нуждается в формуле с постоянной глубиной, по крайней мере, квадратичной в S или суперполиномиальной в S? Какой самый известный результат такого рода?

В случае, если неясно, что я имею в виду под формулой постоянной глубины, я имею в виду формулу, которая, если вы выписываете в виде дерева (с внутренними узлами, являющимися вентилями И / ИЛИ / НЕ, и оставляющими входные данные), то это дерево имеет константу высота. Эквивалентно, формула постоянной глубины представляет собой схему постоянной глубины, в которой все невходные вентили имеют разветвление 1.

Легко преобразовать контур с постоянной глубиной в формулу с постоянной глубиной той же глубины с увеличением полиномиального размера, делая копии затворов, используемых более одного раза. Если глубина схемы равна а ее размер равен O ( p ( n ) ) , формула будет иметь глубину d и размер O ( ( p ( n ) ) d ) . Поэтому ответ - нет.$d$$O(p(n))$$d$$O((p(n))^d)$

Этот вопрос был полностью решен (с учетом постоянных факторов) недавним результатом Бенджамина Россмана ( http://eccc.hpi-web.de/report/2013/169/ ).

$d$$S$$d$$S^d$

$d$$d$$S = O(n^3)$$\sqrt{\log n}$$S^{\Omega(d)}$

(Забыл сказать это раньше: спасибо Бенджамину Россману за то, что он сообщил мне об этом результате.)