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

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

Семинар лаборатории предназначен для обсуждения научных вопросов в области теоретической информатики. На семинаре обсуждение классических результатов в этой области перемежается рассказами о новых результатах сотрудников лаборатории и приглашенных гостей. 
Семинар проводится еженедельно. Информация о докладах приведена ниже.
Семинар проходит в здании НИУ ВШЭ на Покровском бульваре, 11  по средам с 18:10 до 19:30 в аудитории D109.
Для прохода в здание требуется пропуск.
Для оформления пропуска нужно прислать свои ФИО менеджеру лаборатории Дине Чернышовой на адрес dchernyshova@hse.ru.

Kristoffer Arnsfelt Hansen "Computational Complexity of Computing Nash Equilibrium Refinements"
The motivation for introducing Nash equilibrium refinements is to eliminate undesirable equilibria, e.g., those relying on playing dominated strategies.  From a computational perspective the interesting question is whether imposing such restrictions incur a significant additional computational cost. We answer this question for a range of different equilibrium refinements.

David Purser "The Big-O Problem for Labelled Markov Chains"
Given two labelled Markov chains, consider the problem of whether one is big-O of the other. More concretely, the problem asks whether the probability of every finite word in the first chain is smaller than some constant multiple of the probability in the second. We show that the problem is, in general, undecidable. Even when it is known one is big-O of the other, the problem of finding or approximating the optimal constant in the big-O is also undecidable. Our main results show the big-O problem is coNP-complete for unlabelled Markov chains (i.e. when the alphabet consists of a single character) and decidable for weighted automata with bounded languages subject to Schanuel’s conjecture.
Joint work with Dmitry Chistikov, Stefan Kiefer and Andrzej Murawski.

Илья Воробьев (Сколтех) " Multistage Group Testing "
Group testing is a well-known search problem that consists in detecting of sdefective members of a set of t samples by carrying out tests on properly chosen subsets of samples. The test outcome is positive if the tested set contains at least one defective element; otherwise, it is negative. The goal is to find all defective elements by using the minimal possible number of tests in the worst case. Two types of algorithms are usually considered. In adaptive group testing, at each step, the algorithm decides which group to test by observing the responses of the previous tests. In non-adaptive algorithms, all tests are carried out in parallel. Multistage algorithms are a compromise solution to the group testing problem. In p-stage algorithms, all tests are divided into p stages. Tests from the i-th stage may depend on the outcomes of the tests from the previous stages. In this talk, I will present some recent results about multistage group testing.

Manfred Buchacher "Inhomogeneous Lattice Walks"
A lattice walk is a sequence of points in Z^d, their consecutive differences are called its steps, and the set they are taken from its step set. We consider walks whose step set is not fixed but governed by a finite (deterministic) automaton. Closely related to the problem of counting lattice walks, either exactly or asymptotically, is the problem of determining the nature of the associated generating function, i.e. determining whether it is rational, algebraic or D-finite. We explain how what is known as the kernel method generalizes and applies to the setting of inhomogeneous lattice walks to answer this question. This is joint work with Manuel Kauers.

Jie-Hong Roland Jiang "Evaluation and Certification of Quantified Boolean Satisfiability"
Quantified Boolean Formulas (QBFs) allow compact encoding of decision problems even complete in the PSPACE complexity class. The broad applications of QBF satisfiability have attracted recent efforts to develop effective solvers regardless of its intractability. In this talk, we will address two key aspects, evaluation and certification, of QBF solving to enable practical applications.

10.10.19( четверг), аудитория R207
Антон Гнатенко "Спецификация и верификация конечных автоматов-преобразователей"
Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Для формальной спецификации и верификации реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционные темпоральные логики. В докладе будет предложена расширенная темпоральная логика Reg-CTL*, в которой темпоральные операторы параметризованы регулярными выражениями. Мы рассмотрим алгоритмы верификации автоматов-преобразователей относительно формул некоторых фраментов этой логики, а также её выразительные возможности. На правах "work in progress" будет изложена идея алгоритма верифкации относительно произвольных формул Reg-CTL*.

Gleb Pogudin "Solving equations in sequences"
Consider any recurrence relation, for example, the one for Fibonacci numbers: $f_{n + 2} = f_{n + 1} + f_n$. One can think of this equations as a relation between the sequence itself and its shifts. A natural general framework that would incorporate equations of this sort would be a language including not only arithmetic operations, but also a shift operator S. In this language, the above recurrence will recast to $S^2(f) = S(f) + f$. Many questions about nonlinear recurrences and discrete-time dynamical systems can be stated as questions about solutions of equations in this extended language (so-called difference equations) in the ring of sequences. In 2007, Hrushovski and Point showed that the first order theory of sequences in this language is undecidable, that is, there is no algorithm for verifying correctness of first-order formulas. On the other hand, in our recent work with A. Ovchinnikov and T. Scanlon, we have shown that the problem of determining existence of a solution of a system of difference equations in the complex-valued sequences is decidable. In the talk, I will describe this decidability result as well as undecidability results from our recent preprint with T. Scanlon and M. Wibmer that show that almost all reasonable extensions of the consistency problem are, in fact, undecidable including determining the existence of a solution in real-valued sequences and membership problem for radical difference ideals.

Bruno Bauwens "Strongly invertible function and their use for fast data compression"
We say that a probabilistic function F: X -> Y is (K,epsilon)-invertible if with probability 1-epsilon, the value F(x) identifies x inside any subset of K elements in X. More precisely, there exists a deterministic function g that takes a K-element subset of X and an element y as input, such that for all K-element sets S and x in S: Pr [g(S,F(x)) = x] > 1-epsilon This property is stronger than what is typically obtained from hashing, because the recovery of x does not require the knowledge of the randomly chosen hash function. We show that there exist polynomial time constructions of (2^k,epsilon)-invertible functions F: {0,1}^n -> {0,1}^m for which m-k < log^2 (n/epsilon). The functions are obtained from extractors constructed by Guruswamy, Umans, Vadhan, JACM, 2009. Application 1. We consider compression of a string x towards a target size m, (m is smaller than the length of x). In other words, we consider compression functions that have x and m as input and must generate an m-bit description of x. We show that we can speed up any such compressor to a polynomial time one, at the cost of slower decompression and a polylogarithmic increase in the compression length. Moreover, we obtain polynomial time compression down to the Kolmogorov complexity of the string (up to an additive polylog term), provided a good upper bound of this complexity is given. Unfortunately, the result is theoretical, since the decompression time increases by a factor 2^m. Application 2. In distributed compression, several sources need to compress their own strings in isolation. The compressed strings are sent to a decompressor, which needs to reconstruct all strings. If these strings contain correlated information, not all sources need to send all of the information. The minimal sizes of the messages are given by the Slepian-Wolf theorem for sequences generated by a stationary ergodic process. Our second result generalizes this theorem by removing any assumption on the generating mechanism. Moreover, the invertible functions above provide polynomial time compression to this optimal length. We present simplified constructions with improved parameters compared to the papers:
- B.Bauwens and M.Zimand, Linear list-approximation for short programs (or the power of a few random bits), CCC 2014, http://arxiv.org/abs/1311.7278
- M.Zimand, Kolmogorov complexity version of Slepian-Wolf coding, STOC 2017, Montreal, June 19-23, 2017 http://arxiv.org/abs/1511.03602
- B.Bauwens, Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: tighter versions and simple proofs, 2018, https://arxiv.org/abs/1802.00750

Вадим Гринберг (TTIC) "Полуслучайная задача о скрытой клике"
Задача о поиске клики максимального размера в графе является одной из ключевых в современной теоретической информатике. Она NP-трудна, более того, не известно даже хороших аппроксимационных алгоритмов (а приблизить лучше O(n^delta) для некоторого delta вообще невозможно, если P != NP). Эти обстоятельства намекают на то, что в общей постановке задача является неразрешимой за полиномиальное время. Естественным шагом будет перейти от произвольных графов к случайным, и придумывать алгоритмы, решающие задачу с большой вероятностью по распределению на графах. Одними из наиболее популярных являются распределения на графах со скрытой кликой G(n, p, k). Устроены они так: сначала берётся случайный граф на n вершинах и вероятностью появления ребра p = p(n) — G(n, p). Затем выбирается случайное подмножество его вершин размера k = k(n), из которого делается клика (проводятся недостающие рёбра). Возникает вопрос: при каких значениях параметров p и k существует полиномиальный алгоритм, с вероятностью стремящейся к 1 находящий максимальную клику в G(n, p, k)? В 1998 году был представлен полиномиальный алгоритм поиска максимальной клики в G(n, p, k) для любого константного p и k >= Omega(sqrt(np/q)), где q = 1 - p. После этого было создано ещё несколько лучших полиномиальных алгоритмов, обобщающих результат для практически всех возможных функций p = p(n). Однако, неизвестно, существует ли полиномиальный алгоритм, находящий максимальную клику в G(n, p, k) при k = o(sqrt(np/q)), даже в случае константного p. Есть множество результатов, показывающих неработоспособность тех или иных подходов при данных p и k (например, спектральных методов или метода сумм квадратов). Для конкретных p и k >= Omega(sqrt(np/q)) рассмотрим граф со скрытой кликой размера k. Если исходных граф и скрытую клику брать не случайными, а произвольными, задача очевидно становится NP-трудной, но если граф и скрытая клика оба случайные, задача решается за полином (почти для всех p). Насколько важную роль играет случайность? Попытки ответить на этот вопрос приводят к полуслучайной постановке задачи о скрытой клике. Рассмотрим распределение AG(n, p, k). Как и раньше, сначала генерируется случайный граф G(n, p). Затем некий всесильный противник (adversary) выбирает произвольное подмножество из k вершин на своё усмотрение, и делает из него клику. Можно ли гарантировать существование полиномиального алгоритма поиска максимальной клики в AG(n, p, k), вне зависимости от действий противника? В докладе речь пойдёт о результатах, полученных в ходе совместной работы с Dr. Uriel Feige из Weizmann Institute of Science. Будет доказано, что для любых функций p = p(n), НЕ стремящихся к 1 с ростом n, существует полиномиальный алгоритм, с вероятностью стремящейся к 1 находящий максимальную клику в AG(n, p, k) при k >= Omega(sqrt(np/q)), вне зависимости от действий противника. В случае же, когда p = p(n) стремится к 1, поиск максимальной клики в AG(n, p, k) является трудной задачей. Мы докажем, что если существует алгоритм, с константной вероятностью находящий максимальную клику в AG(n, p, k) с p = 1 - 1/poly(n) при k >= Omega(sqrt(np/q)), то NP = RP.

Matthias Englert "The (Generalized) Reordering Buffer Management Problem"
In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrives online, and has to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server. Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance traveled by the servers.
This problem was  introduced by Chan et al. (Theoretical Computer Science 2012) and has been subsequently studied in an online setting by Azar et al. (STACS 2014). The problem is a natural generalization of two very well-studied problems: the k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. In this paper we consider the GRBM problem on a uniform metric in the online version. We give an introduction into this problem and outline a O(log k * (log k + loglog b)) competitive online algorithm. This is a significant improvement in the dependency on b compared to the previous best bound of O(b^0.5 * log k), and is asymptotically optimal for constant k, because Omega(log k + loglog b)$ is a lower bound for GRBM on uniform metrics. (Based on joint work with Harald Räcke and Richard Stotz.)

Matjaž Krnc "Positive Aging Admits Fast Asynchronous Plurality Consensus"
We study the problem of distributed plurality consensus among nodes, each of which initially holds one of opinions. The goal is to eventually agree on the initially dominant opinion. We consider the synchronous communication model in which each node is equipped with a random clock. If the clock of a node ticks, it may open communication channels to a constant number of other nodes, chosen uniformly at random or from a list of constantly many node addresses acquired in some previous steps. The tick rates and the time delays for establishing communication channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed atomically.
Previously, asynchronous plurality consensus has mostly been considered in the Poisson clock model (or similar) without any channel delays. We consider distributions for the waiting times between ticks and channel delays that have constant mean and the so-called positive aging property. In this more general setting asynchronous plurality consensus is fast: if the initial bias between the largest and second largest opinion is at least, then after time steps all but a fraction of nodes have the initial majority opinion. Here denotes the initial ratio between the largest and second largest opinion. After additional steps all nodes have the same opinion w.h.p., and this result is tight.
Next, we further improve partial consensus in the case when the distributions mentioned above satisfy an additional property, which is common in many well-known distributions (e.g., exponential, Rayleigh or Weibull with shape parameter at least). In particular, we show that positive aging together with this property leads to consensus time for all but nodes, w.h.p. For a large range of initial configurations, this result implies that partial consensus can be reached significantly faster in this asynchronous communication model than in the synchronous setting with the same limitations on the number of communication partners per time step.
To obtain these results, we first apply our approach in the classical synchronous model. Then, we focus on the asynchronous model: first, we assume the existence of a centralized leader and finally we present two fully distributed algorithms, which do not rely on any predefined leader.

Martin Milanic "Generalizations of simplicial vertices and a new polynomially solvable case of the maximum weight clique problem"
A vertex in a graph is simplicial if its neighborhood forms a clique. In the talk I will discuss three generalizations of the concept of simplicial vertices: avoidable vertices (also known as OCF-vertices), simplicial paths, and their common generalization avoidable paths. A general conjecture on the existence of avoidable paths will be presented, which, if true, would imply results due to Ohtsuki, Cheung, and Fujisawa from 1976 and due to Chvátal, Sritharan, and Rusu from 2002. In turn, both of these results generalize Dirac's classical result on the existence of simplicial vertices in chordal graphs. Very recently (on August 13, 2019) Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut announced a proof of the conjecture on arXiv.
An application of the concept of avoidable vertices to the maximum weight clique problem will be presented. A graph is said to be hole-cyclically orientable if it has an orientation such that every induced cycle of length at least four is oriented cyclically. These graphs form a generalization of the class of 1-perfectly orientable graphs and their subclasses chordal graphs and circular-arc graphs. By showing that Lex-BFS computes a bisimplicial elimination ordering on these graphs, which is simultaneously a circular-arc elimination ordering, we derive an efficient algorithm that computes a maximum weight clique of a given vertex-weighted hole-cyclically orientable graph. This is the first known polynomial-time algorithm for the maximum clique problem in the class of 1-perfectly orientable graphs.
The existence of avoidable vertices and edges has interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.
Joint work with J. Beisegel, M. Chudnovsky, V. Gurvich, and M. Servatius.

Peter Gacs "Eroders"
This talk is about cellular automata on a finite-dimensional lattice---a certain kind that has special interest for error correction.  A state 0 is distinguished, and a cellular automaton is called an "eroder'' if it eliminates any finite island of non-0s.  We restrict attention to cellular automata whose state set is ordered with 0 being minimal, and whose transition rule is monotonic.  (For example majority vote over some neighbors.)  A classical result of Toom characterizes all 2-state eroders (in any dimension).  It also shows that such eroders erode in linear time, and resist (low random) noise.  (The latter was key to building the simplest known construction of a reliable computation model.)
Here I will report on work (some of it old by Galperin and Toom, some of it new, joint with Ilkka Törmä and Mathieu Hilaire) trying to extend these results to more than 2 states.  In one dimension, all eroders erode in linear time, but not all resist noise.  In 2 dimensions and 3 states, some eroders need more than linear time, and we don't even know whether the eroder property is decidable. Characterizing eroders that resist noise (in any dimension) seems easier than to characterize just eroders (they all erode in linear time).

Khaled Elbassioni "Some Applications of the Multiplicative Weights Update Method in (Semi) Infinite (Discrete) Optimization"
Standard (continuous or discrete) optimization problems typically assume that the dimension and the number of constrains in the problem are finite. In many practical situations, either one or both of these two parameters may be infinite. Examples include: (i) the art gallery problem from computational geometry, where it is required to guard the infinite set of points of an art gallery with the minimum number of cameras, and (ii) robust optimization problems, in which the coefficients of the constraints and/or the objective function are drawn from some infinite uncertainty sets, and the goal is to solve the optimization problem for the worst-case choice in each uncertainty set. In this talk, we ​highlight some of these examples, and then describe how the well-known multiplicative weights update method can be applied to derive efficient approximation algorithms for solving this type of problems.

Kazuhisa Makino "The complexity issues on stochastic games"
Stochastic games were introduced in 1953 by Shapley for the discounted case, and extended to the undiscounted case in 1957 by Gillette. Each such game is a dynamic game with probabilistic transitions played by two players on a finite set of states. The game is played in the infinite sequence of rounds. In the round, the game is in some state. The players choose actions. Then they receive payoffs and the game moves to a new random state, where the payoffs and the transition probability depend on the previous state and the actions chosen by the players. The procedure is repeated at the new state. Stochastic games generalize parity games, cyclic games, simple stochastic games, and BWR games, which all belong to NP and coNP, but are not known to be solved in polynomial time. In this talk, I briefly survey the algorithmic issues on these games, as well as the properties on the optimal strategies for them. I also discuss recent works obtained with Endre Boros, Khaled Elbassioni, and Vladimir Gurvich.

А. Рубцов "Автоматы с дополнительными структурами данных"
Автоматы с магазинной памятью являются одним из основных практических приложений теории автоматов (для компиляции). Они являются частным случаем автоматов с дополнительной структурой данных (ДСД). В 60-х годах были начаты исследования общего случая (J. E. Hopcroft, J. D. Ulman, S. Ginsburg). Эти исследования касались в основном вопросов разрешимости базовых задач: проверки принадлежности слова языку, распознаваемому автоматом с ДСД и проверки языка, распознаваемого ДСД на пустоту. Были получены результаты, связывающие разрешимость этих задач как для односторонних, так и для двусторонних автоматов с ДСД.
Мы обобщаем часть известных результатов, перейдя от вопросов разрешимости к вычислительной сложности. Мы уточняем определение автоматов с ДСД известных как Balloon Automata, и это уточнение гарантирует хорошие структурные свойства для языков, распознаваемых автоматами с ДСД. Также это уточнение приводит к новому и простому методу доказательства нижних оценок на проблему пустоты: для трудности в классе C достаточно доказать, что автомат с ДСД распознаёт язык соответствующий классу сложности C (в роли C могут выступать, например, NP и PSPACE). Эта техника была успешно применена для автоматов со словарём (Set Automata) открытых в 2014 г. М. Кутрибом, А. Мальхером и М. Вендландтом (конференции DLT и DCFS). Основной результат исследования —  сложность проблемы пустоты для автоматов с ДСД совпадает со сложностью языков, распознаваемых машиной Тьюринга на логарифмической памяти с ДСД.


В. Подольский "Балансирующие семейства множеств и пороговые схемы глубины 2"
Семейство S_1,…,S_k подмножеств n-элементного множества называется балансирующим, если для произвольного подмножества X размера n/2 найдется S_i, пересекающееся с X по половине элементов S_i. Недавно было доказано, что размер k такого семейства не меньше n/2 (с точностью до слагаемого o(n)). Этот результат доказывается несложным применением полиномиального метода.
Из результата о балансирующих множествах вытекает новая нижняя оценка для задачи о вычислении функции голосования от n переменных схемой глубины 2, использующей функции голосования от меньшего числа k переменных в качестве элементов. А именно, удается доказать, что k не меньше n/2 для случая, когда никакой элемент схемы не получает на вход одну и ту же переменную несколько раз.
Доклад основан на статье by Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff https://eccc.weizmann.ac.il/report/2019/026/

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


Ranko Lazic «Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games»
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games, a key technical component of which is constructing (explicitly or implicitly) an automaton that separates languages of words encoding plays that are (decisively) won by either of the two players. Our main technical result is a quasi-polynomial lower bound on the size of such separating automata that nearly matches the current best upper bounds. This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games. The key and fundamental concept that we introduce and study is a universal ordered tree. The technical highlights are a quasi-polynomial lower bound on the size of universal ordered trees and a proof that every separating safety automaton has a universal tree hidden in its state space.

Д. Талецкий "Исследование количества максимальных и наибольших независимых множеств в некоторых классах деревьев"
Первая часть доклада посвящена задаче максимизации количества наибольших независимых множеств. Для любого n в классе деревьев со степенями всех вершин не более чем d, где d >= 3, были полностью описаны все n-вершинные деревья, имеющие максимальное количество наибольших независимых множеств среди всех таких деревьев. При этом в случае четного n экстремальное дерево всегда единственно, а в случае нечетного n единственность может и не иметь места. Аналогичный результат получен и для класса n-вершинных деревьев, имеющих ровно l листьев, где 3 <= l <= n-1. В этом случае экстремальное дерево единственно при любых значениях параметров n и l.
Во второй части доклада рассматриваются две задачи о перечислении максимальных независимых множеств.
Для любого n > 3 полностью описаны n-вершинные деревья, не содержащие листьев-дубликатов, имеющие наименьшее количество максимальных независимых множеств среди всех таких деревьев. Кроме того, для полных q-арных деревьев получена асимптотика количества максимальных независимых множеств при высоте деревьев, стремящейся к бесконечности для случая q=2 и для случая всех достаточно больших значений q.

Д. Жук "Сложность задачи удовлетворения ограничениям в зависимости от языка ограничений"
Многие комбинаторные проблемы могут быть выражены как задачи удовлетворения ограничениям (раскраска графа, решений систем уравнений и т.д.)
Известно, что для некоторых языков ограничений задача решается за полиномиальное время, а для некоторых языков является NP-полной, поэтому возникает проблема классификации сложности задачи удовлетворения ограничениям в зависимости от языка допустимых ограничений.
В 1998 году в работе Федера и Варди было высказано предположение, что для любого языка ограничений задача либо решается за полиномиальное время, либо NP-полна. Позднее была сформулирована гипотеза (известная под названием CSP Dichotomy Conjecture) о том, как выглядит граница между полиномиальными и NP-полными случаями, а именно задача решается за полиномиальное время, если есть слабая функция почти единогласия, сохраняющая язык ограничений, и задача NP-полна в остальных случаях.
NP-полнота была доказана еще в 2001 году, а в 2017 году появилось сразу два алгоритма, которые решают задачу за полиномиальное время в случае, если язык ограничений допускает слабую функцию почти единогласия, а следовательно каждый из них завершает доказательство гипотезы и решает проблему, которая была открыта более 20 лет.
Об одном из этих алгоритмов и пойдет речь в данном докладе.

А. Милованов "Игры на машинах Тьюринга и сила случайных строк"
В статье [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings. Information and Computation, 222:80–92, 2013. ICALP 2011 Special Issue] доказываются верхние оценки на классы P^R и NP^R, где R - множество слов большой колмогоровской сложности. В ходе доказательства возникает некоторая конечная игра на машине Тьюринга. Задача определения игрока с выигрышной стратегией принадлежит классу EXPSPACE. 

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

А. Стороженко "Нижние оценки тестирования двудольности с помощью коммуникационной сложности"
В докладе рассматриваются нижние оценки для тестирования двудольности. 
Предполагается, что алгоритм получает граф в виде оракула и может посылать запросы о ребрах и вершинах. Мы используем подход Eden и Rosenbaum (2018), при котором нижние оценки получаются с помощью сведения сложных задач коммуникационной сложности к задачам на графах. 
Будут обсуждаться сравнения различных моделей графов и нижняя оценка $\Omega(1/\epsilon)$ тестирования двудольности плотных графов. Также мы обсудим связь коммуникационной сложности и разрешающих деревьев в рамках используемых сведений.

Д.Сироткин "Исследование вычислительной сложности задач о независимом множестве и о вершинной k-раскраске в некоторых классах графов"
В докладе рассматриваются некоторые локальные преобразования графов, ориентированные на редукцию данных в задачах о независимом множестве и о вершинной 3-раскраске. При помощи данных преобразований, а также новых приемов алгоритмической теории графов, устанавливается вычислительный статус актуальных подзадач данных задач. А именно, устанавливается вычислительный статус задачи о независимом множестве для некоторых подклассов класса планарных графов, а также задачи о вершинной 3-раскраске в некоторых подмножествах множества планарных графов и в некоторых наследственных классах, определяемых запрещенными порожденными структурами малого размера.

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

Д. Пионтковский "Алгебраические системы и формальные языки"
В ряде случаев элементы в бесконечных алгебраических системах или в линейных базисах таких систем удается перечислить с помощью известных формальных языков. Таков классический случай ассоциативной алгебры (или полугруппы), заданной конечным числом мономиальных соотношений: ее линейный базис является регулярным языком. В частности, соответствующая производящая функция, которая описывает рост алгебры, рациональна (теорема Говорова). Естественным обобщением служат введенные Уфнаровским автоматные ассоциативные алгебры: это ассоциативные алгебры, в которых нормальный базис составляет регулярный язык.
В первой части доклада будет дан частичный ответ на вопрос Уфнаровского: верно ли, что конечно определенные ассоциативные алгебры линейного роста автоматны? Будет показано, как эта гипотеза (и аналогичная гипотеза для конечно определенных полугрупп) связана, с одной стороны, со строением регулярных языков линейного роста (slender languages), а с другой -- с теоремой Сколема-Малера-Леха о линейных рекуррентных последовательностях, ее обобщениях и контрпримерами к ней для полей положительной характеристики.
Во второй части будут обсуждаться примеры конечно определенных ассоциативных алгебр и полугрупп (недавно построенных автором вместе с Р. Ла Скала и Ш. Тивари), в которых мономиальные базисы пространства соотношений составляют однозначные контекстно свободные языки, и препятствия, которые возникают при вычислении асимптотики роста таких алгебр.
В третьей части будут обсуждаться алгебраические системы произвольного класса, заданного системой алгебраических операций и тождеств между ними. Если тождеств конечное число, а сами они близки к полилинейным мономиальным (например, тождество ассоциативности), то базис конечно определенной мономиальной алгебраической системы составляет детерминированный контекстно свободный язык. Как следствие, производящая функция этого языка алгебраическая, что дает оценки на асимптотический рост алгебраической системы.

М. Вялый "Алгоритмы подсчета перманента и разрешающие деревья с линейными запросами"
Будет рассказано об обобщении подхода Пойя-Кастелейна к вычислению перманента (0-1)-матриц. Вместо расстановок знаков на матричных элементах используются множители из подходящей алгебры мономов.
Возникающая мера сложности матриц обощает понятие пффафовых графов.
Интересный возникающий в этой связи вопрос — обобщение критерия пффафовости двудольного графа (теорема Литтла). В одну сторону оценка легко получается. В другую — пока нет.


А. Шень "Конструктивизация и множества нулевой меры (обзор)"
В теории меры рассматриваются множества нулевой меры. Как и другие классические понятия, это понятие имеет эффективные варианты (впервые такой вариант был предложен Мартин-Лёфом). Мы обсудим, как и зачем этот эффективный вариант применяется, и как можно эффективизировать некоторые классические результаты, касающиеся эргодической теории (эффективная эргодическая теорема по Вьюгину и др.)

В. Гурвич "Функции Шпрага-Гранди (ШГ) игры НИМ на гиперграфе"
Мы рассматриваем следующее, весьма широкое, обобщение игры НИМ.
Имеется $n$ кучек содержащих $х_1, ..., х_n$ камней и задан произвольный гиперграф $H$ на множестве вершин $V = \{1,..., n\}$. Ход состоит в выборе любого ребра $e \in H$ и (строгом) уменьшении  всех кучек $i \in e$. Игрок, не имеющий хода проиграл (в нормальной версии игры и выиграл в мизерной). Игра называется НИМ на гипперграфе  $H$ и обозначается НИМ-$H$.
Случай $H = \{(1), ..., (n)\}$ соответствует обычной игре НИМ; далее, $H = \{S \subset V | |S| \le k\}$, где $1 \le k \le n$ соответствует игре Мура $НИМ-k$ ; и $H = \{S \subset V | |S| = k\}$, где $1 \le k \le n$ соответствует игре точный $НИМ_k$.
Бутон решил НИМ, вычислив $P$-позиции (0-позиции) в 1901-м. Фактически, он дал явную формулу для функции ШГ (которая была формально введена только в конце 30-х). Мур вычислил 0-позиции своей игры в 1910-м, определив функцию $М(х)$, обобщающую функцию Бутона. В 1962-м Клод Берж утверждал в своей книге "Гиперграфы", что $М(х)$ в точности совпадает с функцией ШГ. Однако, в 1980-м Дженкинс и Майберри показали, что это верно, лишь когда одна из  функций принимает значение 0 или 1. Т.е. 0- и 1-позиции вычислить легко, но уже при $n=4$ и $k=2$ явной формулы для функции ШГ нет. Однако Дженкинс и Майберри нашли такую формулу при $n = k+1$.
Три года назад мы ввели и изучили игру точный $НИМ_k$. Случай $n < 2k$ оказался простым. При этом функция ШГ в $х$ равна максимальной длине партии, начинающейся в $х$. Напротив, случай $n2k$ чересчур сложен: даже 0-позиции неизвестнны. Попробуйте сыграть хотя бы при $n = 5$ и $k = 2$. (Пять кучек камней и брать нужно ровно из двух.) Интереснее всех оказался случай $n = 2k$. При этом функция ШГ задаётся в точности функцией Дженкинса и Майберри для НИМ Мура, только одна из переменных определяется "немного" по-другому.
Оказывается, это не случайное совпадение. Мы нашли очень широкий класс гиперграфов, для которых функция ШГ даётся формулой Дженкинса и Майберри.

А. Чистопольская "Глубина разрешающих деревьев с XOR-запросами больше гранулярности"

Я расскажу про новую нижнюю оценку для глубины дерева с XOR-запросами, разрешающего булеву функцию f. Для этого будем использовать понятие гранулярности булевой функции f. Гранулярность это наименьшее натуральное число k такое, что все коэффициенты Фурье функции f представимы в виде произведения целого числа и 1/2^k. Будет доказано, что глубина дерева с XOR-запросами, разрешающего булеву функцию f, больше, либо равна k+1. 
Эта нижняя оценка является улучшением нижней оценки через число коэффициентов Фурье функции f, не равных нулю, и оценки через степень функции f над полем F_2. Используя полученную нижнюю оценку, можно посчитать точную глубину разрешающих деревьев с XOR-запросами для булевых функций MAJ и итерированный MAJ. Для функции MAJ глубина равна n-B(n)+1, где B(n) — это количество единиц в двоичном представлении числа n. Для итерированного MAJ глубина равна (n+1)/2. Также я расскажу пример функции, для которой эта нижняя оценка не является точной.


V. Grinberg "LP-based approximation of Minimum k-Star Cover"
Consider the following problem: we are given two sets in a metric space, facilities and clients, and an integer k. A star is a pair of one facility and a subset of clients assigned to this facility, and the weight of a star is sum of distances from the facility to assigned clients. We need to select a subset of at most k facilities and assign every client to exactly one of the selected facilities, creating stars, so that the maximal weight of a star (over all stars created) is minimal. This problem is NP-hard, and in spite of resembling k-Facility Location, k-Median or their capacitated versions, it is one of the most poorly studied problems of that kind.
My talk will be devoted to approximation algorithm, based on standard LP relaxation. I will show that, unless we are allowed to violate the number k of opened stars, the integrality gap of standard LP is unbounded, and if we can open at most (1 + eps)k stars, it is Omega(1/eps), for any eps > 0. I will also present a polynomial time approximation algorithm, which opens at most (1 + eps)k stars, and the cost of the returned solution is no worse than O(1/eps^2) times the true (unrelaxed) optimum.

Alexander Kozachinskiy "Data structures for polynomial evaluation".

The talk will be devoted to the polynomial evaluation problem. We are given an univariate polynomial of degree at most n with coefficients in some finite field and we want to answer queries of the form: for a point in a field, what is the value of our polynomial on this point? I will present a lower bound of Larsen which states that for data structures of size linear in n query time should be at least logarithmic in n. This is the strongest known lower bound for static data structures.
I will also give an upper bound of Kedlaya and Umans. They constructed a data structure for polynomial evaluation of size nearly linear in n with polylogarithmic query time.

V.Podolskii “Complexity of dense linear operators”
Suppose we have a vector x of n Boolean variables and we want to compute a Boolean operator Ax with Boolean square matrix A. That is, for all rows of A we would like to compute an OR of variables of x that has ones in the corresponding coordinate of the row. We start with variables and in one step we are allowed to apply OR operation to two expressions computed on previous steps (we build a circuit consisting of OR gates).
If A is a sparse matrix (has O(n) ones), this can easily be done in O(n) operations. We show that the same is true for very dense matrices (O(n) zeros).
This result translates to computation of operators over arbitrary commutative semiring. We also show that that the same cannot be done for semirings with large enough amount of non-commutativity.

Michael Raskin "Clique-width based graph algorithms"
Many graph problems (for example, checking 3-colourability) are known to be NP-complete. But it turns out that they are fixed-parameter tractable, i.e. there are notions of graph structural complexity such that many problems are easy even for large graphs with low complexity.
In the talk, I will explain the notion of clique-width of the graph and show how to optimise a term-automata-based colouring algorithm based on the clique-width representation for counting the colourings with large number of colours.

Д. Дагаев, А. Суздальцев "Оптимальные посевы в турнирах на выбывание".
Перед началом турнира на выбывание проводится заполнение турнирной сетки - этот процесс называется посевом. Есть много способов посеять участников турнира. В данной работе рассматривается задача поиска посева, который максимизирует суммарный зрительский интерес к турниру в предположении, что зрители заинтересованы, при прочих равных, смотреть матчи с высокой конкурентностью (между командами, близкими по силам), а также, при прочих равных, матчи высокого качества (с участием более сильных команд). Эта задача является задачей дискретной оптимизации. Мы решаем эту задачу при двух предположениях: 1) целевая функция линейна по качеству и конкурентности матча; и 2) более сильная команда побеждает более слабую с достаточно большой вероятностью. Оказывается, что в зависимости от значений параметров только два класса посевов могут быть оптимальными. Один из них включает посев, который часто используется на практике; второй является в некотором смысле противоположным. Ослабляя предположение о линейности целевой функции, мы получаем, что эти два класса посевов продолжают оставаться оптимальными при достаточно общих предположениях.

D. Chistikov 
"On the complexity of quantified integer programming".
Quantified integer programming is the problem of deciding assertions of the form "for all/there exists x_k ... for all x_2 there exists x_1 such that A x >= c", where vectors of variables x_k, ..., x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes.
We show that quantified integer programming with alternation depth k is complete for the k-th level of the polynomial hierarchy.
Joint work with Christoph Haase.


D. Chistikov "Navigating one-counter automata: Directions in the mountains".
One-counter automata (OCA) are finite-state automata with a counter that supports increments, decrements, and tests for zero. They correspond to an intermediate class between regular and context-free languages and are suitable for modeling ``counting'' phenomena. However, reasoning about OCA is often intractable: for example, language equivalence is undecidable for nondeterministic OCA, and for deterministic OCA it took 40 years to prove the existence of short distinguishing words.
In this talk, I will give a review of OCA and reasoning tasks for them and discuss two tractability results:
(1) shortest paths between configurations of OCA are of at most quadratic length;
(2) the Parikh (commutative) image and sub-/superword closures of the language are accepted by small nondeterministic finite automata.

Г. Евстропов "The k-sum metric combinatorial optimization problem"

Consider we have some set A and non-negative cost function w(e) of its elements, some subsets of set A are considered to be feasible. For example, A can be a set of arcs of directed graph and we are interested in simple paths from s to t. Well-known problems ask to find a subset of minimum total cost (minsum path can be solved with Dijkstra's algorithm) or a path of minimax length (bottleneck problem). K-sum optimization generalizes these two by asking to find a feasible subset that minimizes the sum of k most expensive elements. In case some subset consists of less than k elements we set its cost in k-sum metric equal to their sum.
It turns out if an O(P(n)) time algorithm exists to find minisum subset, k-sum optimum can be found in O(P(n) * n) time. In case there will be enough time we may consider the same approach for k-sum approximation and some continuous problems (such as k-sum mincost flow).


Г. Пособин "Random noise increases Kolmogorov complexity"
Consider a binary string x of length n whose Kolmogorov complexity equals \alpha n for some \alpha<1. We want to increase the complexity of x by changing a small fraction of bits in x This is always possible: Buhrman, Fortnow, Newman and Vereshchagin showed that the increase can be at least \delta n for large n (where \delta is some positive number that depends on \alpha and the allowed fraction of changed bits).
We consider a related question: what happens with the complexity of x when we randomly change a small fraction of the bits (changing each bit independently with some probability p)? It turns out that a linear increase in complexity happens with high probability, but the guaranteed increase is smaller than in the case of arbitrary change. We note that the amount of the increase depends on x (strings of the same complexity could behave differently), and give an exact lower and upper bounds for this increase (with o(n) precision).
The proof uses the combinatorial technique that goes back to Ahlswede, Gacs and Korner (1977).


А. Ромащенко "Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts"
We propose necessary  conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity.
Using this technique we provide examples of effective and  non-sofic  shifts  on ZZ^2 with very low block complexity: the number of admissible patterns of size NxN grows only as a polynomial in N.

В. Гринберг "Sum-of-squares подход к оптимизации полиномов"
Как известно, задача максимизации многочленов степени 4 и выше является NP-трудной. Несмотря на это, существуют различные алгоритмы, позволяющие найти хорошее приближение оптимальной точки за субэкспоненциальное (и даже квази-полиномиальное) время. Я расскажу об одном из методов, основанном на технике sum-of-squares релаксации. Её суть заключается в сведении исходной задачи оптимизации к задаче поиска вероятностного распределения (в терминах его моментов) на пространстве допустимых решений. Получив некоторое распределение, по нему конструируется новое, сосредоточенное в одной точке, довольно-таки близкой к оптимальной. С ярчайшей стороны данный подход проявляет себя в задаче максимизации полинома с неотрицательными коэффициентами на единичной сфере, которую мы и будем рассматривать.

Ю. Нестеров "Implementable Tensor Methods in Unconstrained Convex Optimization"
In this talk we discuss new tensor methods for unconstrained convex optimization which are solving the auxiliary problems of minimizing convex multivariate polynomials. We analyze the simplest scheme, based on minimization of a regularized local model of the objective function, and its accelerated version obtained in the framework of estimating sequences. Their rates of convergence are compared with the worst-case lower complexity bounds for corresponding problem classes. Finally, for the third-order methods, we suggest an efficient technique for solving the auxiliary problem, which is based on the recently developed relative smoothness condition. With this elaboration, the third-order methods become implementable and very fast.  At the same time, in many important cases the computational cost of iterations in these methods remains on the level typical for the second-order schemes.

А. Милованов "Дерандомизация PIT и обобщения теоремы Сильвестра-Галлаи"
В докладе будет рассказано о некоторых достижениях в области дерандомизации задачи равенства нулю многочлена (в частных случаях). Одним из важных инструментов в этой проблематике является теорема Сильвестра-Галлаи: 
На вещественной плоскости дано конечное число точек, причём такое, что любая прямая, проходящая через две из данных точек, содержит еще одну данную точку. Тогда все данные точки лежат на одной прямой.
Мы обсудим доказательства обобщений этой теоремы, их применения для решения задачи равенства нулю многочлена, а также некоторые открытые вопросы, связанные с её алгебраической версией.
Доклад будет основан на следующих статьях:
Ankit Gupta, Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties.
Nitin Saxena, Progress on Polynomial Identity Testing.

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff, Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.


А. Рубцов "Exile of Kolmogorov Complexity from KC-DCF-Lemma"
We present a new structural lemma for deterministic context free languages. The lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by M. Li and P. Vitányi in 1995 and corrected by O. Glier in 2003. We show that in the case of proving that a language is not a DCFL (the main application of lemmata) the lemmata are equivalent. The structural lemma is much easier to apply than KC-DCF-Lemma. It also provides a new insight to the nature of DCFL.  It allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.


В. Гринберг "L0-сэмплирование и эскизы графов"
В задачах стриминга широкое применение находят так называемые "эскизы" (sketches) —- преобразование входных данных, понижающее их размерность, так, что по эскизу мы сможем восстановить некоторую информацию о потоке. 
Эскизы являются адаптивной структурой — могут изменяться по мере поступления новых данных, и делать это быстро. Я собираюсь рассказать об L0-сэмплерах — линейных эскизах (то есть, являющихся линейными отображениями), позволяющих за малую память по образу вектора получить какую-то его ненулевую координату (если таковые есть). Кроме того, будет рассказано об эффективном по памяти  потоковом алгоритме (также эскизе), основанном на L0-сэмплерах, который по графу, заданному в виде потока рёбер (запросы "добавить ребро", "удалить ребро"), восстанавливает список его компонент связности и остовный лес.

В. Подольский "
A game approach to the sensitivity conjecture"
The famous sensitivity conjecture has many reformulations. 
One of them states that the decision tree complexity of any Boolean function is polynomially related the sensitivity of this function.
In this talk we will discuss a recently introduced communication game that can help to prove the sensitivity conjecture.
The talk is based on the paper “A New Approach to the Sensitivity Conjecture” by Justin Gilmer, Michal Koucký and Michael E. Saks (ITCS 2015).


Л. Сысоева "Некоторые свойства автоматного замыкания множеств булевых функций"
Рассматривается задача о реализации булевых функций автоматными формулами специального вида с произвольной последовательностью подаваемых наборов.
На множестве булевых функций вводится операция автоматного замыкания: рассматриваются автоматные формулы --- формулы над конечным множеством автоматов, таких, что в каждом состоянии автомата функция выхода содержится в некотором исходном множестве булевых функций. Считается, что автоматная формула реализует булеву функцию, если при последовательной подстановке в некотором порядке всех наборов значений переменных функции в каждый момент времени значение формулы совпадает со значением булевой функции на текущем входном наборе значений переменных. Для введенной операции автоматного замыкания получено описание всех автоматно замкнутых классов булевых функций.
Для классов булевых функций, сохраняющих константы, явно построены автоматные формулы глубины n-1, такие, что для любой булевой функции f от n переменных из соответствующего класса, существует последовательность двоичных наборов, такая, что при подаче наборов этой последовательности на построенную автоматную формулу реализуется функция f.

Е. Минеева "Параметризованная сложность вычислений"
Все, кто знаком с алгоритмами, знают, что, как правило, в сложностную оценку времени работы алгоритма или затрат по памяти входит не только длина входа (которую обычно выбирают параметром в классической теории сложности), но и какие-то другие параметры — возьмите, например, обход в глубину, время работы которого зависит от количества вершин и ребер в графе. Таким образом довольно естественно возникает желание рассматривать сложность задачи относительно некоторых параметров. Кроме того, глядя, например, на NP-полные задачи, возникает ощущение, что какие-то из них более сложные, а какие-то менее: например, 3-COLORING уже NP-полна, а 3-VERTEX-COVER решается за полиномиальное время. На основе этих идей возникло ответвление теории сложности вычислений — параметризованная сложность. Я расскажу о FTP — одном из базовых сложностных классах в данной теории, а также про некоторые техники, которые используются в данной области: branching, iterative compression, а также kernelization. Рассказ является обзором базовых лекций, которые были рассказаны на школе-конференции Recent Advances ​in Parameterized Complexity.


Michael Raskin "Complementing unambiguous finite automata (a superpolynomial lower bound for 1-letter alphabet)"
Two main approaches to finite automata are deterministic finite automata and nondeterministic finite automata. Deterministic finite automata can be easily combined to recognize the union, intersection or the complement of the languages recognized by original DFAs; but they might require many more states than nondeterministic finite automata.
Unambiguous finite automata are NFAs that have at most one accepting run for every word. They can be exponentially more succinct than DFAs in some cases, and there was a conjecture that recongnizing the complement of the language of an UFA can be done by another UFA with a polynomial increase in the state count (the best lower bound was quadratic).
In the talk, a superpolynomial lower bound for complementing a UFA over the one-letter alphabet will be presented.

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.


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

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.


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

Ю. Макарычев "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.

К. Макарычев "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.

Т. Исхаков "Краткое введение в потоковые алгоритмы" 
Доклад посвящен потоковым алгоритмам: через алгоритм проходит большой поток данных, а размер имеющейся памяти ограничен. В докладе будут разобраны подходы, позволяющие находить: количество различных элементов, наиболее частые элементы, 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 Petrović "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 и отправьте нам уведомление. Спасибо за участие!
Сервис предназначен только для отправки сообщений об орфографических и пунктуационных ошибках.