Пороговым элементом называется сумма входных переменных с целыми коэффициентами (весами). Он выдает единицу, если эта сумма положительна. Максимальная абсолютная величина коэффициентов порогового элемента называется его весом. Персептроном степени d называется булева схема глубины 2 с пороговым элементом на верхнем уровне и произвольными булевыми элементами входной степени не выше d на нижнем уровне. Весом персептрона называется вес его порогового элемента.

Для всякого d>1 мы строим персептрон степени d, требующий веса порядка $n^{\Omega(n^d)}$, то есть вес всякого персептрона степени d, вычисляющего ту же булеву функцию, должны быть не меньше $n^{\Omega(n^d)}$. Эта оценка точна: всякий персептрон степени d эквивалентен персептрону степени d и с весом порядка $n^{O(n^d)}$. В случае пороговых элементов (т. е. $d=1$) результат был получен Хастадом; мы используем технику Хастада.