• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Коллоквиум в 2015/2016 году

21 июня 2016 года

Критические наследственные классы графов

Дмитрий Малышев, НИУ ВШЭ


Одним из возможных способов преодоления алгоритмической сложности NP-полных задач на графах является сужение, т.е. наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений, т.е. принадлежности графа некоторому классу, приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается NP-полной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно, переходя от рассмотрения отдельных классов графов к рассмотрению каких-либо представительных семейств классов графов. В докладе рассматривается семейство наследственных классов графов, т.е. классов, замкнутых относительно удаления вершин. Также рассматриваются так называемые критические классы графов, т.е. классы графов, играющие особую роль в анализе сложности задач на графах в семействе наследственных классов. В докладе речь пойдет об известных критических классах для ряда задач на графах и соответствующих следствиях для анализа их сложности.

 Афиша коллоквиума (PDF, 236 Кб)



14 июня 2016 года

Теория сложности доказательств

Александр Разборов, Университет Чикаго/МИАН

Теория сложности доказательств изучает насколько простыми могут (или не могут) быть формальные доказательства истинных утверждений в различных естественных системах доказательств. Классы рассматриваемых утверждений и систем могут существенно варьироваться в зависимости от контекста, что определяет целый ряд неожиданных и важных взаимосвязей между теорией сложности доказательств и многими областями в математике и компьютерных науках. Весьма значительную часть всей теории занимают пропозициональные доказательства, т.е. доказательства бескванторных утверждений, представимых в языке логики высказываний.

В своём обзорном докладе я попытаюсь дать по необходимости краткое введение в эту последнюю область. Две темы, которым я планирую уделить особое внимание ввиду их актуальности, таковы:
1. Система резолюций и практические алгоритмы для выполнимости булевых формул.

2. Алгебраические и полуалгебраические системы доказательств и комбинаторная оптимизация.

Если останется время, я также расскажу о своих собственных последних результатах в этих направлениях.

 Афиша коллоквиума (PDF, 325 Кб)


 

31 мая 2016 года

К теории формирования социальных групп

Константин Сорокин, НИУ ВШЭ

60 лет назад Чарльз Тибу высказал гипотезу о том, что свободный выбор места жительства способствует сортировке людей согласно их предпочтениям и, как следствие, оптимальному производству общественных благ. Ключевая идея была в том, что голосование ногами играет роль «невидимой руки», только на рынке общественных благ. К сожалению, Тибу не предложил адекватного математического аппарата для проверки своего утверждения. С тех пор было предпринято много попыток построить общую теорию предоставления общественных благ — или, другими словами, общую теорию формирования социальных групп, но всегда результат существенно уступал аналогичной теории общего равновесия для частных благ. В докладе будет представлен обзор существующих достижений в этой области, а также оригинальный подход, позволяющий снять существенное число накопившихся сложностей. Наши основные результаты — доказательство теоремы существования экономического равновесия в очень общих предположениях и исследование его основных свойств — эффективности и устойчивости. 

 Афиша коллоквиума (PDF, 278 Кб)

10 мая 2016 года

Causal inference and Kolmogorov complexity


Bruno Bauwens, НИУ ВШЭ
It is often stated that “Correlation does not imply causation”: a dependency between observed values of two random variables might not imply that there exists a causal connection between the corresponding processes (and assuming there exists one, one might not know the direction). In Shannon information theory, this is reflected by the law of “symmetry of information”: I(X;Y) = I(Y;X). The information that a random variable X has about Y equals the information that Y has about X. This law remains valid if Shannon entropy is replaced by Kolmogorov complexity. However, there exists a subtler setting where this law is violated and one might speculate that this asymmetry can be used to reconstruct causality. In the second part of the talk, we discuss the postulate of independence of conditionals for the inference of causal relations in observed data. This postulate was introduced by D. Janzing and B. Schölkopf in 2010, and the two-variable case states that, if X causes Y, then the marginal distribution PX has low information about the conditional distribution P{Y|X} (as defined with Kolmogorov complexity). We explain how the most popular methods can be explained by this postulate and overview new methods that were inspired by it.

 Афиша коллоквиума (PDF, 119 Кб)





26 апреля 2016 года

Синтез изображений с помощью глубоких нейросетей


Виктор Лемпицкий, Сколковский Институт Науки и Технологий (Сколтех)

Глубокие нейросети за последние три года научились классифицировать изображения с точностью, почти сравнимой с человеческим мозгом. Но могут ли они синтезировать изображения и потеснить классические методы компьютерной графики и обработки изображений? О первых успехах в этом направлении, достигнутых исследователями за последние два года, пойдет речь в докладе.

 Афиша коллоквиума (PDF, 1.26 Мб)


12 апреля  2016 года

Physics Informed Machine Learning


Michael (Misha) Chertkov, Skoltech - Adjunct Professor, on leave from Los Alamos National Laboratory)

Machine Learning (statistical engineering) capabilities are in a phase of tremendous growth. Underlying these advances is a strong and deep connection to various aspects of statistical physics. There is also a great opportunity in pointing these tools toward physical modeling. In this colloquium I illustrate the two-way flow of ideas between physics and statistical engineering on three examples. First, I review the work on structure learning and statistical estimation in power system distribution (thus physical) networks. Then I describe recent progress in constructive understanding of graph learning (on example of inverse Ising model) illustrating that the generic inverse task (of learning) is computationally easy in spite of the fact that the direct problem (inference or sampling) is difficult. I conclude speculating how macro-scale models of physics (e.g. large eddy simulations of turbulence) can be learned from micro-scale simulations (e.g. of Navier-Stocks equations).

 Афиша коллоквиума(PDF, 265 Кб)


22 марта 2016 года

Finding a majority ball with majority answers


Mate Vizer,  Renyi Institute Budapest

Suppose we are given a set of n balls {b1, …, bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least n/2 times among the n balls. We show that the minimum number of queries needed to solve this problem is Θ(n) in the adaptive case and Θ(n3) in the non-adaptive case. We also consider some related problems. This is a joint work with D. Gerbner, B. Keszegh, D. Palvolgyi, B. Patkos and G. Wiener.

 Афиша коллоквиума (PDF, 495 Кб)


15 марта 2016 года

Decidability of Conjunctive Queries for Description Logics with Counting, Inverses and Nominals


Sebastian Rudolph, TU Dresden

Description Logics (DLs) are Knowledge Representation formalisms with a great significance for Semantic Web technologies. For instance, the ontology specification languages OWL DL and its successor OWL 2 DL, standardized by the World Wide Web Consortium (W3C), are based on DL languages. Conjunctive queries constitute the standard querying paradigm for data bases and have in recent years attracted increasing interest in the area of logic-based knowledge representation. While decidability and computational complexity are mainly clarified for standard DL reasoning tasks (such as knowledge base consistency or axiom entailment), decidability of conjunctive query answering in OWL DL and OWL 2 DL is still an open problem. Over a comparatively long time, a major obstacle towards the solution of this problem was the intricate interplay of three modeling features: nominal concepts, inverse roles and cardinality constraints. In my talk, I will present results that, for the first time, establish decidability of a DL containing all three constructs. For a slightly restricted class of conjunctive queries (i.e., queries with only simple roles), our result also shows decidability in the logics that underpin OWL DL and OWL 2 DL. This work was carried out in the course of a research stay at Oxford University and has been published in the Journal of Artificial Intelligence Research

 Афиша коллоквиума (PDF, 199 Кб)


1 марта 2016 года

Современная лингвистика и компьютерные технологии

Ольга Ляшевская – к.ф.н., профессор факультета гуманитарных наук НИУ ВШЭ
Борис Орехов  – к.ф.н., доцент факультета гуманитарных наук НИУ ВШЭ
Екатерина Рахилина – д.ф.н., профессор факультета гуманитарных наук  НИУ ВШЭ

Что такое лингвистическая ошибка? Можно ли ее вычислить? Автоматически найти? Исправить? Предупредить? Об этой и других задачах современной лингвистики расскажут сотрудники Школы лингвистики НИУ ВШЭ.

 Афиша коллоквиума (PDF, 192 Кб)


9 февраля 2016 года

Алгоритмы на графах во внешней памяти

Максим Бабенко, ФКН НИУ ВШЭ и компания «Яндекс»

Алгоритмы на графах (построенные в предположении, что граф достаточно мал, чтобы его описание помещалось в оперативной памяти) представляют собой один из наиболее подробно изученных разделов computer science. С ростом объема графа, однако, эти методы перестают быть применимы, т.к. внешняя память (например диск) обладает существенно иным соотношением времени доступа и пропускной способности.

В докладе будет дан обзор известных методов работы с графами в модели внешней памяти, показаны типичные трудности, возникающие при адаптации классических алгоритмов, а также сформулирован ряд открытых вопросов.

 Афиша коллоквиума (PDF, 673 Кб)



2015

22 декабря 2015 года

Блеск и нищета математических методов в прикладных исследованиях

Александр ШаповалФКН НИУ ВШЭ

Я собираюсь напомнить примеры прикладных исследований, в которых математическая компонента, видимо, не воспринимается серьёзно большинством математиков. В качестве «затравки» сразу вспоминается взорвавшая интернет история о «странности» отечественных выборов, якобы «доказанная математически». Или проблема глобального потепления, ужасные последствия которого чуть ли не полностью просчитаны на современных суперкомпьютерах. Подробно будет рассказано о методологии прогноза сильных землетрясений и способах оценки эффективности алгоритмов, осуществляющих прогноз. Если по окончании доклада кто- нибудь из незаинтересованных слушателей согласится с тем, что в нем была представлена научная область, которая может развиваться на факультете компьютерных наук, то я буду считать свою задачу выполненной.

 Афиша коллоквиума (PDF, 103 Кб)



1 декабря 2015 года

Простота и сложность задач оптимизации

Юрий Нестеров
CORE (Брюссель) и ФКН НИУ ВШЭ

Теория оптимизации, возникшая на стыке математики и инженерных дисциплин, поневоле наследует противоречия между этими классическими областями знаний. Только правильная расстановка приоритетов при выборе и определении основных понятий (размер данных, размерность и т. д.) позволяет построить математически строгую теорию методов оптимизации, интересную как математикам, так и инженерам. Именно о таких приоритетах пойдет речь в докладе.

С другой стороны, есть все основания утверждать, что устройство окружающей нас природы и общества основано на мощнейших оптимизационных принципах – именно тех, которые и нужны для решения задач сверхбольшого размера. Понимание и математическое обоснование этих принципов, по–видимому, и будет основным стимулом для развития теории и методов оптимизации в ближайшее время.

 Афиша коллоквиума (PDF, 205 Кб)


24 ноября 2015 года

Что такое квантовая информатика?

Александр Холево, Математический институт им. В.А. Стеклова РАН и МИЭМ НИУ ВШЭ

Квантовая теория информации — научная дисциплина, изучающая общие закономерности передачи, хранения и преобразования информации в системах, подчиняющихся законам квантовой механики. Квантовая теория информации использует математические модели для исследования потенциальных возможностей таких систем, разрабатывает принципы их рационального и помехоустойчивого дизайна. Попутным результатом развития идей квантовой теории информации является существенное прояснение логической структуры квантовой теории, ее оснований и соотношения с реальностью.

 Афиша коллоквиума (PDF, 110 Кб)


17 ноября 2015 года

k-Anonymization by Freeform Generalization

Panagiotis Karras, Skoltech

Syntactic data anonymization strives to (i) ensure that an adversary cannot identify an individual’s record from published record attributes with high probability, and (ii) preserve data utility. These mutually conflicting goals can be expressed as an optimization problem with privacy as the constraint and utility as the objective function. Conventional research on k-anonymity, a popular privacy model, has resorted to generalizing data values in homogeneous groups. However, such grouping is not necessary. Instead, data values can be recast in a heterogeneous manner that allows for higher utility. Nevertheless, previous work in this direction did not define the problem in the most general terms; thus, the utility gains achieved are limited. In this paper, we propose a methodology that achieves the full potential of heterogeneity and gains higher utility. We formulate the problem as a network flow problem and develop an optimal solution therefor using Mixed Integer Programming, an O(kn2) greedy algorithm that has no time-complexity disadvantage vis-á-vis previous approaches, an O(kn2 log n) enhanced version thereof, and an O(kn3) adaptation of the Hungarian algorithm; these algorithms build a set of k perfect matchings from original to anonymized data. Our techniques can resist adversaries who may know the employed algorithms. Experiments with real-world data verify that our schemes achieve near-optimal utility (with gains of up to 41%), while they can exploit parallelism and data partitioning, gaining an efficiency advantage over simpler methods.

 Афиша коллоквиума  (DOCX, 71 Кб)


10 ноября 2015 года

Обучение с запросами, формулы Хорна и формальные понятия

Сергей Объедков, НИУ ВШЭ

В традиционной постановке задачи обучения с учителем мы располагаем набором данных, разбитым учителем на несколько классов, и стремимся реконструировать принцип, лежащий в основе этого разбиения. Что, если данных нет, но есть сам учитель, готовый отвечать на наши вопросы? Какие вопросы и в какой последовательности нужно задавать, чтобы как можно быстрее обучиться интересующему нас понятию? 

Мы рассмотрим базовые принципы обучения с запросами и разберем некоторые простые алгоритмы, работающие в такой модели. Подробнее остановимся на задаче обучения формуле Хорна, для которой существует полиномиальный алгоритм обучения с запросами. Эта задача тесно связана с задачей вычисления базиса импликативных зависимостей, выполняющихся в данных, которая изучается, в частности, в анализе формальных понятий. Можно ли превратить полиномиальный алгоритм обучения с запросами в полиномиальный алгоритм обучения по данным, эффективно имитируя учителя? Ответ пока неизвестен.


27 октября 2015 года

Морфологические методы анализа формы данных

Юрий Визильтер, ГосНИИАС

Что такое «форма» данных — одномерной кривой, двумерного изображения, трехмерной фигуры, многомерного облака точек? Интуитивно понятно, что «форма» характеризует такие особенности пространственно распределенных данных, которые сохраняются при определенных типах их преобразований, либо характерны не только для данного конкретного экземпляра данных, но для некоторого класса или множества таких объектов, обладающих определенным семантическим сходством. Но как математически формализовать это понятие? Однозначного и универсального ответа на этот вопрос до сих пор нет, хотя теорий форм и основанных на них соответствующих методов обработки и анализа данных (прежде всего, изображений) создано множество.

Математическая морфология (mathematical morphology, MM) была исходно предложена и развита в работах Ж. Серра, П. Марагоса и др., как теория формы, основанная на описании образов (изображений) в виде комбинации других (базовых) образов при помощи операций некоторой выбранной алгебры. В то же время Ю. П. Пытьевым был независимо предложен морфологический подход к анализу изображений (морфология Пытьева, МП), предназначенный для решения задач оценки сходства, взаимной привязки, выделения отличий между изображениями, сравнения изображений (форм) по сложности, оценки сходства/различия форм. В настоящее время оба этих алгебраических подхода, а также целый ряд геометрических подходов, рассматриваемых в рамках таких направлений, как shape matching и manifold learning, образуют современный инструментарий методов описания и анализа формы данных, которые могут быть названы в широком смысле «морфологическими». О базовых идеях, а также последних результатах в этой области пойдет речь в данном докладе.

 Афиша коллоквиума (PDF, 260 Кб)


13 октября 2015 года

Матрицы и тензоры малого ранга в математике и приложениях

Евгений Тыртышников, ИВМ РАН

В докладе будет рассказано о новых направлениях вычислительной линейной алгебры, которые получили развитие в ИВМ РАН за последние 20 лет. Ключевая роль в них принадлежит матрицам малого ранга, которые используются как для представления данных, в том числе многомерных матриц, так и для построения эффективных вычислительных алгоритмов. Мы обсудим различные методы представления и аппроксимации тензоров и связанные с ними математические вопросы, в том числе и открытые, и перспективы новых методов (тензорный поезд и др.), в которых все действия сводятся к матричным операциям.

Новые области применений связаны с задачами оптимизации, в частности для докинга при разработке лекарственных препаратов и для идентификации параметров в моделях математической иммунологии. Получены также новые эффективные методы для специальных классов нестационарных задач, в частности для так называемого основного кинетического уравнения, и новые подходы к численному решению уравнений типа Смолуховского.

 Афиша коллоквиума (PDF, 286 Кб)



29 сентября 2015 года

Formal Concept Analysis: A Useful Example of Modern Mathematics

Bernhard Ganter, Technische Universität Dresden

We give impressions of a field of research that was started some 30 years ago under the name of “Formal Concept Analysis.” It is a mathematical theory, based on algebraic structures such as complete lattices, with a spectrum of applications in data analysis and knowledge processing.

Although the theory is advanced and substantial, it finds more attention in computer science than in mathematics. Indeed, the field has some potential for supporting recent developments of structured knowledge representations.

In our lecture, we introduce the very basic notions of the field, show the possibility of expressive graphical representations, discuss some applications and, eventually, demonstrate why the value of this development lies in its mathematical nature.

Афиша коллоквиума (PDF, 520 Кб)


22 сентября 2015 года

Extinction probabilities of branching processes with infinitely many types

Sophie Hautphenne, EPFL Lauzanne and University of Melbourne

We present some iterative methods for computing the global and partial extinction probability vectors for branching processes with countably infinitely many types. The probabilistic interpretation of these methods involves truncated branching processes with finite sets of types and modified progeny generating functions. Simple probabilistic arguments and coupling methods are used to prove the convergence of the algorithms. In addition, we discuss extinction criteria for global and partial extinction.

Афиша коллоквиума (PDF, 336 Кб)


15 сентября 2015 года

Случайные графы

Андрей Райгородский, Московский государственный университет имени М. В. Ломоносова

В 1959 году П. Эрдеш и А. Реньи начали изучать биномиальную модель случайного графа G(np), в которой ребра графа на n вершинах возникают взаимно независимо с одной и той же вероятностью p. За прошедшие десятилетия наука о случайных графах Эрдеша-Реньи сделалась одной из центральных дисциплин в области комбинаторики и ее приложений.

Одно из наиболее естественных обобщений модели Эрдеша-Реньи состоит в следующем: берется некоторая последовательность графов Hn, и в каждом из графов Hn ребра сохраняются взаимно независимо с одной и той же вероятностью p. Возникают случайные графы Hn, p. В последнее время очень много исследований посвящено именно такому варианту модели Эрдеша-Реньи.

Мы расскажем об одной последовательности графов, важной для комбинаторной геометрии и теории кодирования. Для этой последовательности графов мы рассмотрим описанный выше вариант модели Эрдеша-Реньи и обсудим различные старые и новые результаты, которые здесь удалось получить. В частности, речь пойдет о раскрасках таких случайных графов, об их кликовых числах и их числах независимости.

Афиша коллоквиума (PDF, 504 Кб)


Что было в 2014/2015 году

Юрий Нестеров

CORE (Брюссель)
и ФКН НИУ ВШЭ

Простота
и сложность
задач оптимизации