Козачинский А.Н., Верещагин Н.К. Экспандеры, коммуникационная, вопросная сложность (10.10.2018)

Заседание НИСМЛ 05.12.2018. Докладчики: Козачинский Александр Николаевич, Верещагин Николай Константинович Тема: Экспандеры и связь коммуникационной и вопросной сложности Аннотация: Доклад посвящён техникам получения нижних оценок для трёх видов сложности вычислений: схемной (рассматривавшейся начиная с 1950-х годов), коммуникационной и вопросной. Будет описана техника сведения одних оценок к другим и приведены результаты автора, относящиеся к ограниченности этой техники.