Теоретическая информатика и комбинаторика

«Теоретическая информатика и комбинаторика» — это совместный научный семинар ФИВТ МФТИ и ФКН ВШЭ. Семинар проводится 1-2 раза в семестр. Одна из задач семинара — обеспечить научное взаимодействие между факультетами в области теоретической информатики и комбинаторики. Заседания семинара проводятся попеременно на ФКН и в МФТИ. Страница семинара доступна также на сайте МФТИ.

Заседания:

23 марта 2017 г. (МФТИ)
В. Подольский «Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates» 
Анонс


19 октября 2016 г. (ФКН, аудитория 505, 18:10-19:30)
А. Скопенков «Stability of intersections of graphs in the plane and the van Kampen obstruction»

A map $\varphi:K\to \R^2$ of a graph $K$ is approximable by embeddings, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ embedding $f:K\to\R^2$. Analogous notions were studied under the names of cluster planarity and weak simplicity. We present criteria for approximability by embeddings (P. Minc, 1997, M. Skopenkov, 2003) and their algorithmic corollaries.
A map $\varphi:K\sqcup L\to \R^2$ of the disjoint union of graphs $K$ and $L$ is {\bf approximable by maps with disjoint images}, if for each $\varepsilon>0$ there is an $\varepsilon$-close to $\varphi$ map $f:K\sqcup L\to\R^2$ such that $f(K)\cap f(L)=\emptyset$. We present open problems on this notion.
We introduce the van Kampen (or Hanani-Tutte) obstructions for these properties, as well as their generalizations to higher dimensions and to $r$-tuple intersections. We present the completeness result of this obstruction (D. Repov\v s and A. Skopenkov, 1998) and its algorithmic corollary.

21 сентября 2016 г. (МФТИ, 18:30-20:00) 
А. Коротин, Н. Верещагин «Самоподобные замощения плоскости многоугольниками» 
В докладе будет рассказано о некоторых известных и не очень классах замощений плоскости (замощения Пенроуза, Амманна, Амманна-Бинкера, L-замощения и др.) Будет рассказано, как они определяются и какими интересными свойствами обладают (напр. самоподобность, апериодичность).

9 марта 2016 г. (ФКН, аудитория 509, 16:40-18:00) 
М. Тихомиров «Геометрические графы и сложность их распознавания» 
Классические дистанционные графы — это графы, которые можно  нарисовать на плоскости так, чтобы все ребра были отрезками длины 1,  возможно, пересекающимися. С дистанционными графами связано много  известных задач, таких как проблема Эрдеша о количестве единичных  расстояний среди n точек и проблема о хроматическом числе плоскости. 
Возникает естественный вопрос: можно ли придумать алгоритм, эффективно распознающий дистанционные графы (а может быть, и позволяющий рисовать их на плоскости)? Оказывается, что нет, такая задача NP-трудна. Такую же задачу можно рассматривать в пространствах других размерностей, а также для других разновидности геометрических графов, т.е. графов с вершинами в точках пространства и ребрами, которые соответствуют некоторому геометрическому соотношению (например, расстояние = 1). 
Рассказ будет про ряд результатов в этой области и некоторые подходы к их доказательству.