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

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

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


22.11.2017

Guilhem Gamard  "Quasiperiodicity on one and two-dimensional words. Continuation of previous talk: two-dimensional aspects"

We work on one-dimensional and two-dimensional words, i.e. colorings of ℤ and ℤ² with colors choosen among a finite alphabet. These objects are fundamental in several branches of computer science, thus a large amount of research is devoted to understanding how “symmetric” a word can be: for example we have the notions of periodicity, topological entropy, minimality, unique ergodicity…

Here we focus on quasiperiodicity: a finite pattern q is a quasiperiod of a word w iff w is covered with translated copies of q, which may overlap. We would like to understand the structure of q-quasiperiodic words only through properties of q. One motivation for this comes the study of quasicrystals in physics, where a 2-dimensional word represents a regular molecular structure and a quasiperiod is a configuration with local minimal energy.


08.11.2017
А. Шень "Что такое геометрическое построение и как доказывать невозможность такового"

До появления компьютеров у людей было некоторое интуитивное понятие алгоритма, которое можно было сравнивать с различными его уточнениями (предложенными в 1930-е годы) - и доказывать несуществование алгоритма, используя эти уточнения. Аналогичная ситуация была с "геометрическими построениями": решение задачи на построение тоже можно считать своего рода алгоритмом. Однако тут ситуация была парадоксальной: люди доказывали неразрешимость задач, не имея определений. Любопытно вышло с "доказательством Гильберта невозможности построить центр круга одной линейкой" (существует проективное преобразование, сохраняющее круг, но сдвигающее центр) - оно не было опубликовано, но упоминалось в работе Кауэра с более сильным "результатом" - невозможность построения центра двух непересекающихся кругов, лежаших вне друг друга. Потом люди указывали на "ошибки" в работе Кауэра, но по-прежнему не давая формального определения построения. Мы обсудим возможные варианты такого определения и возможное исправление рассуждения Гильберта для точного определения. (По работе Акопяна и Фёдорова).

01.11.2017

Guilhem Gamard  "Quasiperiodicity on one and two-dimensional words"

We work on one-dimensional and two-dimensional words, i.e. colorings of ℤ and ℤ² with colors choosen among a finite alphabet. These objects are fundamental in several branches of computer science, thus a large amount of research is devoted to understanding how “symmetric” a word can be: for example we have the notions of periodicity, topological entropy, minimality, unique ergodicity…

Here we focus on quasiperiodicity: a finite pattern q is a quasiperiod of a word w iff w is covered with translated copies of q, which may overlap. We would like to understand the structure of q-quasiperiodic words only through properties of q. One motivation for this comes the study of quasicrystals in physics, where a 2-dimensional word represents a regular molecular structure and a quasiperiod is a configuration with local minimal energy.


18.10.2017
В. Чернышев "Динамика точек на метрических графах"

Я планирую рассказать о дискретных задач, которые возникают, если рассматривать задачу Коши для нестационарного уравнения Шредингера на метрических графах или гибридных многообразиях с локализованными начальными данными. Основной акцент я постараюсь сделать на связи со следующими задачами теории чисел:  проблемой подсчета числа целых точек в расширяющих симплексах (будут задействованы многочлены Тодда), задачей о распределении абстрактных простых и теоремой Сколема-Малера-Леха.

11.10.2017
Ю. Макарычев "Algorithmic and Hardness Results for the Hub Labeling Problem"

There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of Ω(log n) for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously.
Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an O(log D) approximation algorithm for graphs of diameter D with unique shortest paths. In particular, we get an O(log log n) approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an O(log n) approximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2.
The talk is based on a joint paper with Haris Angelidakis and Vsevolod Oparin.

03.10.2017
К. Макарычев "Clustering Billions of Reads for DNA Data Storage"

I will tell the audience how to quickly cluster billions of strings based on their similarity (edit distance). We will discuss what makes the problem hard and then explore known (theoretical/mathematical) techniques like Locality Sensitive Hashing (LSH), metric embeddings, and sketching that can be employed for clustering Big Data. Finally, I will show how we use these techniques along with some new ingredients to cluster billions of DNA strands.
I will also briefly mention how string clustering is used in the Microsoft DNA Storage project – the project that develops technology for storing data on synthesized DNA strands (https://www.microsoft.com/en-us/research/project/dna-storage/).
The talk is based on my joint work with a team of researchers from Microsoft Research and University of Washington (https://www.microsoft.com/en-us/research/project/dna-storage/). This paper will appear at NIPS 2017.

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.
 
07.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»

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




 

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