[Коллоквиум]: Раскраски гиперграфов и смежные проблемы: вероятностно-алгоритмический подход

Докладчик: Дмитрий Шабанов - ФКН ВШЭ/МФТИ Ряд известных задач комбинаторики и теоретической информатики (например, задача k-SAT, задача об оценках чисел Рамсея и др.) могут быть сформулированы в абстрактных терминах раскрасок однородных гиперграфов. В докладе будут представлены классические комбинаторные постановки подобных задач и будет рассказано о последних достижениях в их решении. Мы обсудим вероятностные алгоритмы, с помощью которых были получены новые результаты, а также вопрос их практической реали