Введение
1 Нижние оценки 21
Дополнительные определения и обозначения 21
Типы операций и элементов 21
Метод элиминации элементов 22
Упрощение схемы при подстановках 24
Меры сложности схем 25
1.1 Нижняя оценка 7n/3 - O(1) для функций высокой степени 27
1.1.1 Мультипликативная сложность и полиномы над F2 27
1.1.2 Доказательство нижней оценки 28
1.2 Нижняя оценка 3n - o(n) для аффинных дисперсеров сублинейной размерности 32
1.2.1 Аффинные дисперсеры 32
1.2.2 Доказательство нижней оценки 33
1.3 Нижняя оценка (3 + 816)n - o(n) для аффинных дисперсеров сублинейной размерности 36
1.3.1 Схемы с циклами 36
1.3.2 Преобразования циклических схем 40
1.3.3 Однопроходные квадратичные источники глубины два 49
1.3.4 Мера сложности 52
1.3.5 Доказательство нижней оценки 57
1.3.6 Полное доказательство 61
1.4 Нижняя оценка 3.11n для квадратичных дисперсеров субли нейной размерности 77
1.4.1 Квадратичные дисперсеры 77
1.4.2 Доказательство нижней оценки 80
1.5 Нижняя оценка 5n - o(n) в базисе U2 для линейных функций 88
1.5.1 Линейные функции 88
1.5.2 Доказательство нижней оценки 89
1.6 Нижняя оценка 3.24n на схемную сложность в среднем в базисе U2 для дисперсера относительно проекций 95
1.6.1 Предварительные определения и леммы 97
1.6.2 Основная теорема 104
1.6.3 Нижняя оценка на схемную сложность в среднем 107
1.7 Ограничения метода элиминации элементов 114
2 Верхние оценки 117
2.1 Автоматическое нахождение эффективных схем 117
2.1.1 Сведение 118
2.1.2 Верхняя оценка для MOD3n 120
2.2 Верхняя оценка для вычисления всех MOD-функций одновременно 125
2.2.1 Кодировки 126
2.2.2 Вспомогательные блоки 127
2.2.3 Доказательство оценки 131
Заключение 133
Литература 133
