Аннотация:Задача работы — познакомить читателя с основными приемами, используемыми при доказательстве нижних оценок сложности схем из функциональных элементов. Работа носит учебно-методический характер и может рассматриваться как учебное пособие по курсу «Элементы теории сложности схем». Работа самодостаточна, от читателя требуется лишь знакомство с базовыми определениями дискретной математики и теории дискретных функций.
http://new.math.msu.su/department/dm/data/uploads/dm_articles/lower_bounds.pdf