Адрес e-mail:
Прошедшие события
Панельная онлайн-дискуссия на тему «Новая волна. Акселерация будущего»
Онлайн-собрание ректората и студенческого актива института
AI 2020: технологии, рынок и управление продуктами
Родительское собрание в МФТИ
Летняя онлайн-школа «Всероссийский навигатор абитуриентов МФТИ»
Фазли Атауллаханов: «Физика свертывания крови и COVID-19»
Юрий Яровиков: «Какая математика нужна в анализе данных?»
Михаил Бурцев — об экспериментах с Memory Transformer
Даниил Поляков: «Мощь Python на все случаи жизни»
Презентация магистерской программы «Биоинформатика» ФБМФ и Napoleon IT
Александр Львовский: «Квантовая революция как мировой технологический тренд»
Выпускной МФТИ 2020: онлайн-формат не отменяет праздник
Директор ФИАН Николай Колачевский: «Наука и технологии: путь в лидерство»
Онлайн-презентация кафедры космической физики ЛФИ
Сессия вопросов-ответов с биоинформатиком Антоном Буздиным
Презентация магистерской программы «Физика сверхпроводимости и квантовых материалов»
Презентация магистерской программы «Двумерные материалы: физика и технология наноструктур»
Презентация магистерской программы «Цифровые технологии в бизнесе»
Денис Дмитриев: «Особенности поступления и ответы на вопросы. Приемная кампания — 2020»
Всероссийский онлайн-выпускной

Лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems»

Лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems»

28 ноября в 18:30 в Актовом зале ЛК в рамках математического кружка ФПМИ состоится лекция Владимира Колмогорова «Complexity classifications of Valued Constraint Satisfaction Problems».


Аннотация:


Classifying complexity of different classes of optimization problems is an important research direction in Theoretical Computer Science. One prominent framework is Valued Constraint Satisfaction Problems (VCSPs) in which the class is parameterized by a "language", i.e. a set of cost functions over a fixed discrete domain. An instance of the problem is an arbitrary sum of functions fr om the language (possibly with overlapping variables), with the goal to minimize the sum. This framework can capture many classes of optimization problems such as 3-SAT, graph coloring, minimum vertex cover, submodular minimization, and others.

A series of recent papers, culminating with the works of D. Zhuk and A. Bulatov in 2017, have established a complete complexity classification of arbitrary languages. Vladimir will describe their contributions to this topic. One of the results is a reduction from general VCSPs to plain CSPs (i.e. to languages with {0,infinity}-valued functions). The key algorithmic tool that was used is a certain LP relaxation of the problem combined with the algorithm for plain CSPs.


In the second part of the talk Vladimir will consider a version of the CSP framework wh ere each variable must appear in exactly two constraints. It captures, in particular, the class of perfect matching problems, which can be solved by the Edmonds's blossom-shrinking algorithm. Vladimir will present a generalization of this algorithm that can handle "even Delta-matroid constraints". As a consequence of this, researchers settle the complexity classification of planar Boolean CSPs started by Dvořák and Kupec.


Владимир Колмогоров — профессор Института науки и техники (IST), Австрия. Он окончил Московский физико-технический институт в 1999 году. Учёную степень кандидата компьютерных наук получил в Корнельском университете в 2003 году. Основным направлением исследований Владимира является дискретная оптимизация алгоритмов для задач в компьютерном зрении и других областях.

Лекция пройдёт на английском языке.


Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2020 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях