Исследование и построение монотонных схем небольшой глубины для вычисления симметричной пороговой функции

В рамках выпускной квалификационной работы было проведено исследование вопроса вычислимости функции голосования MAJ[n] и приближённой функции голосования AppMAJ[n,ε] монотонными схемами малой глубины, также были доказаны несколько новых оценок на глубину таких схем. Цель заключалась в обобщении существующих результатов, касающихся булевых схем для MAJ[n]/AppMAJ[n,ε]. Для этого была предпринята попытка вывести и доказать новые верхние и нижние оценки на глубину, которые бы зависели от неконстантных параметров n и ε. В результате была получена новая верхняя оценка O(1 + log(1/ε)/log(log(n))) на минимальную глубину unbound fan-in схемы полиномиального размера, вычисляющую AppMAJ[n,ε]. В частных случаях эта оценка также улучшает существующие результаты: с одной стороны, имеем оценку Θ(log(n)/log(log(n))) для обычной MAJ[n] (то есть была получена верхняя оценка, совпавшая с известной ранее нижней); с другой стороны, также имеем константную оценку глубины для AppMAJ[n,ε], ε=1/poly(log(n)).