Четверг, 10 сентября, zoom. Начало в 15:00.
Докладчик: И.Н. Пономаренко (ПОМИ).
Тема: Нижняя оценка на размерность Вейсфейлера-Лемана для циркулянтных графов..
Abstract
Доказано, что проблема изоморфизма циркулянтных графов не разрешима за полиномиальное время комбинаторными алгоритмами типа алгоритма Вейсфейлера-Лемана. Точнее, для бесконечного числа положительных целых чисел n существует циркулянтный граф с n вершинами, у которого размерность Вейсфейлера-Лемана ограничена снизу величиной c\sqrt{\log n} для некоторой константы c>0, не зависящей от n.
