|
|
Научно-исследовательский семинар кафедры дискретной математики ФИВТ МФТИ
5 апреля 2016 г., г. Москва, ул. Льва Толстого, д. 16, Яндекс, БЦ «Морозов», ауд. «Кэмбридж» в ШАД
|
 |
|
 |
|
|
|
Сравнительный анализ методов оценивания бикликового покрытия
М. Попов |
|
Аннотация:
В данном докладе я сравню различные методы доказательства нижних оценок для размера бикликового покрытия графов и расскажу о применении этих оценок в теории коммуникационной сложности. Главным образом сравнивается классический метод трудных множеств (fooling sets в англоязычной литературе) и более новых методов Юкны и Куликова и метода энтропийных неравенств. Также будет рассказано про обобщения этих оценок на случай n-мерного коммуникационного протокола.
|
|
Обратная связь: