| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Научно-исследовательский семинар кафедры дискретной математики ФИВТ МФТИ
|
|||
|
|
|||
|
Сравнительный анализ методов оценивания бикликового покрытия М. Попов |
|||
|
Аннотация: В данном докладе я сравню различные методы доказательства нижних оценок для размера бикликового покрытия графов и расскажу о применении этих оценок в теории коммуникационной сложности. Главным образом сравнивается классический метод трудных множеств (fooling sets в англоязычной литературе) и более новых методов Юкны и Куликова и метода энтропийных неравенств. Также будет рассказано про обобщения этих оценок на случай n-мерного коммуникационного протокола. |
|||