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

Семинар лаборатории теоретической информатики

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

Семинар проводится еженедельно. Для регулярных обсуждений на осенний семестр 2016 года была выбрана тема "Булев анализ Фурье". Информация о докладах приведена ниже.

Семинар проходит на факультете компьютерных наук НИУ ВШЭ по средам с 18:10 до 19:30 в аудитории 505. Для прохода в здание требуется пропуск. Для оформления пропуска нужно прислать свои ФИО менеджеру лаборатории Екатерине Вавиловой на адрес evavilova@hse.ru 


31.05.2017

Т. Исхаков "Краткое введение в потоковые алгоритмы"


Доклад посвящен потоковым алгоритмам: через алгоритм проходит большой поток данных, а размер имеющейся памяти ограничен. В докладе будут разобраны подходы, позволяющие находить: количество различных элементов, наиболее частые элементы, l2-норму, решать задачу динамической связности графа (разумеется, решения будут приближенными).

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


24.05.2017 г.
С.Кузнецов "Категориальные грамматики: логико-математический подход к описанию естественного языка"

Будет рассказано о том, как о синтаксических структурах, существующих в  естественных языках, можно рассуждать в рамках неклассических (точнее, субструктурных)  логических систем.

Идея такого подхода восходит к работам Айдукевича (1930-е гг.) и Ламбека  (1958). Позже оказалось, что предложенные тогда исчисления естественным образом погружаются в  линейную логику Жирара (1987) в её некоммутативном варианте. Современные версии  синтаксических исчислений позволяют описывать самые разнообразные феномены, возникающие в языке (намного более сложные, чем тривиальные примеры вроде "Иван любит Марью"), и успешно  реализованы в виде программ, осуществляющих синтаксический анализ и извлечение  семантики из предложений.

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


10.05.2017 г.
М.Вялый "Неотрицательный и PSD ранги матриц и их связь с классической и квантовой коммуникацией"

Неотрицательный и PSD ранги матриц помимо ясного геометрического смысла имеют прямое отношение к задачам коммуникации.

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


26.04.2017 г.
А. Рязанов "Верхняя оценка на взаимную информацию через ранг матрицы совместного распределения"

Взаимная информация даёт нижнюю оценку на неотрицательные и положительно полуопределённые ранги матриц, которые связаны с возможностью представления многогранника как сечения конусов неотрицательных ортантов или положительно полуопределенных матриц, соответственно. Для многогранников сложных задач в предположении P≠NP неотрицательные и положительно полуопределенные ранги не могут быть полиномиальными по размерности, но построить явные сверхполиномиальные нижние оценки для рангов удалось пока только для некоторых частных случаев.

В докладе будет доказано, что взаимная информация произвольных случайных величин с конечным носителем ограничена сверху логарифмом ранга матрицы совместного распределения этих величин. Тем самым мы покажем, что нижняя оценка на неотрицательный и положително определенный ранги через взаимную информацию не может быть сверхполиномиальной. Также будут рассмотрены другие оценки из статьи T. Lee, Z. Wei, R. de Wolf и для них доказаны аналогичные результаты.


12.04.2017 г. - 19.04.2017 г.
М.Каледин "Применения базисов Грёбнера в задачах целочисленного программирования"

Целочисленное программирование -- важный класс задач комбинаторной оптимизации, которые возникают в практических приложениях и часто являются NP-трудными. Для их точного и приближённого решения существует много методов, возникающих в теории алгоритмов. В докладе будет рассмотрен подход, основанный на использовании торических идеалов, предложенный в начале 90-х годов Конти, Траверсо и Томасом. Мы рассмотрим основные идеи теории базисов Грёбнера для описания идеалов в кольце многочленов от многих переменных и покажем, как с её помощью можно решать основные задачи целочисленного программирования:  оптимизацию и перечисление допустимого множества.


05.04.2017 г.
В. Подольский "Рассказ о конференции STACS 2017"

В докладе планируется коротко рассказать о некоторых работах прошедшей недавно конференции STACS 2017.

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


15.03.2017 г. - 22.03.2017 г.

М. Вялый "Тонкие сводимости"

Неформально говоря, сильная гипотеза об экспоненциальном времени (SETH) утверждает, что самый быстрый способ решить задачу выполнимости (k-SAT)

- это вычислить значение КНФ во всех точках. Эта гипотеза настолько сильна, что имеет все шансы оказаться ложной.

В попытках опровержения SETH возникла интересная техника тонких сводимостей (fine-grained reductions). С помощью этой техники можно связывать гипотезы об оптимальном времени решения задач, имеющих очень разную сложность - от экспоненциальной до квадратичной.

В докладе будут даны точные формулировки SETH и fine-grained reductions, приведены простые примеры тонких сводимостей. Кроме того, обсудим, какую роль в этой технике играет лемма о похудании (sparsification lemma).



09.03.2017 г.
А. Кноп "Теоремы об иерархии по времени для эвристических вычислений"

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

22.02.2017 г. - 03.03.2017 г.

Г. Евстропов "Оптимальные алгоритмы решения некоторых антагонистических игр с упорядоченными множествами монет "

В докладе будут рассмотрены и подробно изложены основные результаты статьи Tomasz Idziaszek, "An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game". Рассмотрим следующую задачу: на столе в ряд выложены монеты, для каждой из которых определена стоимость, игроки по очереди берут одну монету с любого конца ряда, при этом каждый из них играет оптимально и стремится максимизировать разность между суммарной стоимостью своих монет и суммарной стоимостью монет другого игрока. Данная задача может быть легко решена за время O(n^2) с использованием идей динамического программирования, в докладе же планируется рассмотреть решение за линейное время. С использованием этого результата будет решена за квазилинейное время и более общая задача, если монеты образуют не один, а несколько рядов.



15.02.2017 г.

Данила Кутенин "Полиномиальный алгоритм проверки простоты чисел"


 25.01.2017 г. - 01.02.2017 г.

 М. Вялый "Квазиполиномиальный алгоритм решения игр четности"

 Игры четности - важный класс бесконечных игр на графах, интересный и с теоретической точки зрения, и с точки зрения приложений. Решение игр  четности как алгоритмическая задача лежит в пересечении классов NP и  coNP. Полиномиальных алгоритмов решения игр четности неизвестно. Уже  довольно давно были получены субэкспоненциальные алгоритмы решения игр  четности.

 Осенью 2016 года был достигнут неожиданный успех: C.S. Calude, S. Jain,  B. Khoussainov, Wei Li, F. Stephan нашли квазиполиномиальный алгоритм  решения игр четности (Квазиполиномиальный означает экспоненту от  степени логарифма.) Результат получается остроумной сводимостью игр  четности к обычным позиционным играм на ациклическом графе  квазиполиномиального размера. Рассуждения совершенно элементарные, хотя  и  технически громоздкие.

 В докладе будет изложен этот алгоритм.


11 .01.2017 г.
Tomislav Petrovic "A step towards finding an infinite string which is neither random nor predictable"

We'll discuss how to convert a sequential program that uses small amount of space and large amount of time into a parallel program that uses large amount of space and small amount of time, and vice-versa.

We'll also look at a simple extension of this result to sequential programs that don't necessarily use a small amount of space, but for which we know that they visit some small set of states.



7.12.2016 г.
К. Макарычев "Solving Optimization Problems with Diseconomies of Scale".

We present a new framework for solving optimization problems with a  diseconomy  of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as x q , with the amount x of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is A q , where A q  is the q-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for several optimization problems with a diseconomy of scale such asMinimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. In the Minimum Energy Efficient Routing problem, the goal is to route an unsplittable multicommodity flow in a network/graph between terminals so as to minimize the energy consumption on the links/edges. Our analysis relies on a decoupling inequality for nonnegative random variables. Consider arbitrary nonnegative jointly distributed random variables Y 1 ,…,Y n . Let X 1 ,…,X n  be independent copies of Y 1 ,…,Y n  such that all X i  are independent and each X i  has the same distribution as Y i . Then, E(X 1 +…+X n ) q  < C q  E(Y 1 +…+Y n ) q . The inequality was proved by de la Pena in 1990. However, the optimal constant C q  was not known. We show that the optimal constant is C q =A q . This is a joint work with Maxim Sviridenko, Yahoo Labs.


09.11.2016 г. - 16.11.2016 г.

А. Шень  "О нормальных последовательностях".

Нормальные последовательности цифр (или символов) - это самый простой вид случайности:  все комбинации цифр (данной длины) встречаются одинаково часто. Будет рассказано о базовых свойствах таких последовательностей. (Например, почему число 2a обладает таким свойством, если им обладает число a -- в десятичной записи. Почему такие последовательности вообще существуют? Как это связано с автоматами и сложностью?)


02.11.2016 г.

В.В. Опарин “Оценки на сложность вывода в системах доказательств, основанных на методе резолюции”.

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



19.10.2016 г.
А. Скопенков «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.

23.09.2016 г. - 12 .10.2016 г, Основы булева анализа Фурье
Г. Пособин, В. Подольский, А. Милованов, М. Вялый





 

 







 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!