name: Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности
keyword_list: игры Карчмера - Вигдерсона коммуникационная сложность формульная сложность
abstract: Целью данной работы является разработка и совершенствование новых подходов к доказательству нижних оценок на формульную сложность булевых функций с использованием методов коммуникационной сложности. Первая глава содержит необходимые сведения о формулах Де Моргана и коммуникационной сложности. Во второй главе доказывается усиление теоремы Меира - Вигдерсона о предсказании семейством сертификатов. В третьей предлагается полудуплексная модель коммуникационной сложности и доказываются верхние и нижние оценки для функций и отношений. В четвёртой главе доказывается нижняя оценка на коммуникационную сложность блочной композиции универсального отношения и игры Карчмера - Вигдерсона для некоторой функции.
chairman_dissertation_council.name: Максим
chairman_dissertation_council.surname: Всемирнов
chairman_dissertation_council.patronymic: Александрович
chairman_dissertation_council.position: директор
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Член-корреспондент РАН
chairman_dissertation_council.wos_research_id: J-3400-2013
chairman_dissertation_council.scopus_author_id: 23394353400
chairman_dissertation_council.rinc_id: 12091
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Максим
organization_supervisor.surname: Всемирнов
organization_supervisor.patronymic: Александрович
organization_supervisor.position: директор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.47.17
rubrics.name: Математическая теория информации
rubrics.code: 27.03.19
rubrics.name: Математическая логика
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Математическая логика, алгебра и теория чисел
speciality_codes.code: 01.01.06
supervisors.fio: Гирш Э.А.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Математическая логика, алгебра и теория чисел
supervisors.responsible_type: Научный руководитель
opponents.fio: Верещагин Н.К.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
opponents.fio: Ромащенко А.Е.
opponents.scientific_degree: Кандидат физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
protection_organization.short_name: ПОМИ РАН
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В. А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК
protection_organization.ogrn: 1037843013174
protection_organization.supervisor_name: МАКСИМ
protection_organization.supervisor_surname: ВСЕМИРНОВ
protection_organization.supervisor_patronymic: АЛЕКСАНДРОВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: ПОМИ РАН
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В. А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК
author_organization.ogrn: 1037843013174
author_organization.supervisor_name: МАКСИМ
author_organization.supervisor_surname: ВСЕМИРНОВ
author_organization.supervisor_patronymic: АЛЕКСАНДРОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения