• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Препринт
Spatially Adaptive Computation Time for Residual Networks

Figurnov M., Collins M. D., Zhu Y. et al.

arXiv:1612.02297. arXiv. Cornell University, 2016

Глава в книге
Computing majority by constant depth majority circuits with low fan-in gates

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.

Глава в книге
GANs for Biological Image Synthesis

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.

Статья
Correction to the leading term of asymptotics in the problem of counting the number of points moving on a metric tree

V.L. Chernyshev, Tolchennikov A.

Russian Journal of Mathematical Physics. 2017. Vol. 24. No. 3. P. 290-298.

Глава в книге
Stochasticity in Algorithmic Statistics for Polynomial Time

Vereshchagin N., Milovanov A.

In bk.: 32nd Computational Complexity Conference. Вадерн: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1-18.

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


«Теоретическая информатика и комбинаторика» — это совместный научный семинар ФИВТ МФТИ и ФКН ВШЭ. Семинар проводится 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). 
Рассказ будет про ряд результатов в этой области и некоторые подходы к их доказательству.