Москва, Кочновский проезд, д. 3 (недалеко от станции метро "Аэропорт").
ком. 621,624
тел. 8 (495) 772-95-90*22913; *11020
руководитель департамента — Подольский Владимир Владимирович
заместитель руководителя департамента — Соколов Евгений Андреевич
менеджер — Алескерова Инесса Ивановна
Департамент создан в 2014 году, одновременно с созданием факультета компьютерных наук на основе базовой кафедры Яндекса, которая вошла в его состав. Основу департамента составляют научные группы, ведущие исследования мирового уровня в области машинного обучения, теоретической информатики, распределенных вычислений, масштабируемых алгоритмов для обработки больших данных, компьютерного зрения, обработки текстов, информационного поиска и графических моделей.
Figurnov M., Collins M. D., Zhu Y. et al.
arXiv:1612.02297. arXiv. Cornell University, 2016
Kulikov A., Podolskii V. V.
In bk.: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, Germany. Vol. 66. Leipzig: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1-14.
Osokin A., Chessel A., Carazo Salas R. E. et al.
In bk.: Proceedings of the IEEE International Conference on Computer Vision (ICCV 2017). Venice: IEEE, 2017. P. 2252-2261.
V.L. Chernyshev, Tolchennikov A.
Russian Journal of Mathematical Physics. 2017. Vol. 24. No. 3. P. 290-298.
In bk.: 32nd Computational Complexity Conference. Вадерн: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.
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.
9 марта 2016 г. (ФКН, аудитория 509, 16:40-18:00)
М. Тихомиров «Геометрические графы и сложность их распознавания»
Классические дистанционные графы — это графы, которые можно нарисовать на плоскости так, чтобы все ребра были отрезками длины 1, возможно, пересекающимися. С дистанционными графами связано много известных задач, таких как проблема Эрдеша о количестве единичных расстояний среди n точек и проблема о хроматическом числе плоскости.
Возникает естественный вопрос: можно ли придумать алгоритм, эффективно распознающий дистанционные графы (а может быть, и позволяющий рисовать их на плоскости)? Оказывается, что нет, такая задача NP-трудна. Такую же задачу можно рассматривать в пространствах других размерностей, а также для других разновидности геометрических графов, т.е. графов с вершинами в точках пространства и ребрами, которые соответствуют некоторому геометрическому соотношению (например, расстояние = 1).
Рассказ будет про ряд результатов в этой области и некоторые подходы к их доказательству.