О сложности линейных операторов в классе схем глубины 2

В работе предложены методы получения нижних оценок сложности линейных булевых операторов (и связанных с ними матриц) в двух моделях схем глубины 2. В первой модели допустимы только линейные элементы с произвольным числом входов, во второй – произвольные булевы элементы. Методы применимы к матрицам с достаточно большим расстоянием Хемминга между строками, например, к матрицам Адамара.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 05–01–00994, программы “Университеты России”, проект УР.04.02.528, и программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ-1807.2003.01.