ИСТИНА

• Охват: Международная
• Даты проведения: 19-24 июля 2015
• Место проведения: Dagstuhl Shloss, Germany
• Организатор:
  Dagstuhl Seminar
• Число участников: 70
• Число участников из МГУ: 1
• Число докладчиков: 30
• Веб-сайт: http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=15301
• Описание конференции:

  Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g. polynomial-time solvable or non-trivially approximable, fixed-parameter tractable or definable in a weak logic). One of the most striking features of this research direction is the variety of different branches of mathematics (including algebra and logic, combinatorics and graph theory, probability theory and mathematical programming) that are used to achieve deep insights in the study of the CSP, and this seminar will contribute towards further synergy in the area. In the last 7-8 years, research activity in this area has significantly intensified and hugely impressive progress was made, but some of the central questions remain open to date. The main topics addressed during the seminar will include complexity dichotomies for CSP and related problems, approximability of CSPs, parameterized complexity of CSPs, and counting CSPs. The participants will also explore the interactions between these topics.

• Добавил в систему: Жук Дмитрий Николаевич

Доклады:

• 2015 The structure of relations invariant under near unanimity operations (Пленарный)
• Автор: Zhuk D.