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

18.10.2023 Arseny M. Shur "Non-constructive approach to repetition thresholds" 
We analyze a simple algorithm, transforming an input word into a word avoiding certain repetitions such as fractional powers and undirected powers. This transformation can be made reversible by adding the log of the run of the algorithm to the output. We introduce a compression scheme for the logs; its analysis proves that $(1+\frac{1}{d})$-powers and undirected $(1+\frac{1}{d})$-powers can be avoided over $d+O(1)$ letters. These results are closer  to the optimum than it is usually expected from purely information-theoretic considerations.
Видеозапись семинара.

11.10.2023 Dmitry Zhuk  "On the complexity of the Quantified Constraint Satisfaction Problem"
The Quantified Constraint Satisfaction Problem (QCSP) is the generalization of the Constraint Satisfaction problem (CSP) where  both existential and universal quantifiers are allowed. Formally, the QCSP over a constraint language is the problem to evaluate a sentence with both quantifiers, predicates from the constraint language, and conjunctions.
The goal is to describe complexity of this problem for all constraint languages. In 2018 we discovered constraint languages for which the QCSP is coNP-complete, DP-complete, and even $\Theta_{2}^{P}$-complete, which made a complete classification hardly possible. Recently, I obtained several results that make me believe that such a classification is closer than it seems. First, I obtained an elementary proof of the PGP reduction, which allows to reduce the QCSP to the CSP. Second, I showed that there is a gap between $\Pi_{2}^{P}$ and PSpace, and found a criterion for the QCSP to be PSpace-hard. Finally, I found the missing complexity class, and now I believe that for any constraint language the QCSP is either in P, or NP-complete, or coNP-complete, or DP-complete, or $\Theta_{2}^P$-complete, or $\Pi_{2}^{P}$-complete, or PSpace-complete.
Видеозапись семинара.

20.09.2023 Thomas Fernique "Local rules for cut and project tilings"
The cut-and-project method was introduced in the 1980s to define non-periodic tilings, as an alternative to the substitution method. The simplest case is that of a straight line drawn on a grid sheet: the sequence of cut horizontal or vertical segments, projected onto the line, forms a tiling of the line which is non-periodic as soon as the slope is irrational. This extends to higher dimensions (the celebrated Penrose tilings, for example, can be obtained from an algebraic plane in Euclidean space of dimension 5). The same question as for tilings defined by substitution then arises: which of these tilings do admit local rules, i.e. can be characterized only by their patterns of a given finite size? In this presentation, the cut and project method will be presented without assuming any prior knowledge. Then, some remarkable characterizations of (non-)existence of local rules will be presented and illustrated with examples as simple as possible.
Видеозапись семинара

28.06.2023  Nikolay Vereshchagin " Goodman-Strauss theorem and its versions"
Goodman-Strauss theorem theorem states that for any substitution satisfying some conditions the family of substitutional tilings is sofic. Those conditions were not formulated explicitly and the proof is very long (about 70 pages). Therefore is very hard to verify it. Also Goodman-Strauss claims that under those conditions the family of hierarchical tilings is sofic. (Every substitutional tiling is hierarchical, but the other way around.) In an attempt to clarify the statement, Fernique and Ollinger formulated explicitly some requirements for substitutions, under which the family of hierarchical tilings its sofic. In the talk I will state Fernique and Ollinger theorem in all details and prove it in a specific interesting case. This will be the joint session of Kolmogorov seminar and TCS Lab of HSE.
Видеозапись семинара

14.06.2023 Михаил Николаевич Вялый "О проверке выполнимости алгебраических формул над полем из двух элементов"
Будет рассказано о  вероятностном полиномиальном алгоритме проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для  проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для PIT основан на лемме Шварца-Зиппеля, а алгоритм проверки выполнимости основан на лемме Вельянта- Вазирани.
Видеозапись семинара

10.05.2023 Bruno Bauwens "Hall-type theorems for fast dynamic matching and applications"
We show that bipartite graphs with a large expansion factor implies poly(log N) time dynamic matching, where N is the total number of nodes. In this result, we consider dynamic matching in which the opponent makes requests of a node to be matched, and the match must remain unchanged until the request is retracted. Coupled with known constructions of lossless expanders, this gives a solution to the main open problem in a classical paper of Feldman, Friedman, and Pippenger~\cite{fel-fri-pip:j:networks}.

 Application 1: storing sets.
We construct 1-query bitprobes that store a dynamic subset $S$ of an $N$ element set. A membership query reads a single bit, whose location is computed in time $\poly(\log N, \log (1/\epsilon))$ time and is correct with probability $1-\epsilon$. Elements can be inserted and removed efficiently in time $\quasipoly (\log N)$. Previous constructions were static: membership queries have the same parameters, but each update requires the recomputation of the whole data structure, which takes time $\poly(\# S \log N)$. Moreover, the size of our scheme is smaller than the best known constructions for static sets.

Application 2: switching networks.
We construct explicit constant depth $N$-connectors of essentially minimum size in which the path-finding algorithm runs in time quasipolynomial in $\log N$. In the non-explicit construction in Feldman, Friedman and Pippenger 1988, and in the explicit construction of Wigderson and Zuckerman, the runtime is exponential in $N$.
Видеозапись семинара

20.04.2023 (четверг) Владимир Подольский "Constant-Depth Sorting Networks"
We consider sorting networks that are constructed from comparators of arity k>2. That is, in our setting the arity of the comparators — or, in other words, the number of inputs that can be sorted at the unit cost — is a parameter. We study its relationship with two other parameters — n, the number of inputs, and d, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for majority functions from majority gates of lower fan-in. We obtain the first lower bounds on the arity of constant-depth sorting networks. More precisely, we consider sorting networks of depth d up to 4, and determine the minimal k for which there is such a network with comparators of arity k. For depths d=1, 2 we observe that k=n. For d=3 we show that k=n/2. For d=4 the minimal arity becomes sublinear: k=\Theta(n^{2/3}). This contrasts with the case of majority circuits, in which k=O(n^{2/3}) is achievable already for depth d=3. The talk is based on joint work with Natalia Dobrokhotova-Maikova and Alexander Kozachinskiy:https://drops.dagstuhl.de/opus/volltexte/2023/17546/pdf/LIPIcs-ITCS-2023-43.pdf

Видеозапись семинара

12.04.2023 Артем Радомский "Об одной проблеме Эрдеша"
Пусть a_{1}<a_{2}<... --- последовательность натуральных чисел. Обозначим через f(n) количество решений уравнения p+a_{k}=n, где p пробегает множество простых чисел. Мы получаем оценку снизу для f(n). В частности, мы показываем, что lim sup f(n)=\infty. Это отвечает на хорошо известный вопрос П. Эрдеша. 
Видеозапись семинара

10.04.2023  Alexey Slizkov "Computational bounds for the 2048 game"
Совместное заседание семинара Лаборатории и Колмогоровского семинара.
2048 is a single player video game, played by millions mostly on mobile devices. We prove rigorously for the first time that there is an algorithm with winning probability at least 0.99969, and that there is a strategy for achieving the 256 tile guaranteed (with probability 1).
Видеозапись семинара

15.03.2023, 22.03.2023  Александр Козачинский "Weisfeiler–Leman algorithm in space" in 2 parts.
The Weisfeiler–Leman algorithm is a family of (incomplete) graph isomorphism tests having interesting connections to logic, fractional isomorphisms,  tree-width, and etc. We study the power of this algorithm on distance graphs of sets of points in R^d.

Видеозапись: Part 1, Part 2

21.12.2022 Николай Проскурин "Выражение разрешающих списков полиномиальными пороговыми функциями"
Доклад посвящен полиномиальным пороговым функциям - важной модели в теоретической информатике, нашедшей применение в теории сложности вычислений, теории обучения и коммуникационной сложности. В докладе нас интересует эффективное выражение в этой модели класса разрешающих списков, которые можно рассматривать как обобщение классов конъюнкций и дизъюнкций, а также как частный случай разрешающих деревьев. Мы доказываем, что почти для всех d = o(n^(1/3)) разрешающий список может быть выражен полиномиальной пороговой функцией степени d и веса 2^O(n/d^2). Эта оценка является асимптотически оптимальной, так как она соответствует нижней оценке Бейгеля [Beigel, 1994], и улучшает предыдущий результат Клайванса и Серведио [Klivans, Servedio, 2006], в котором вес равнялся 2^O(n log^2(d)/d^2). Для улучшения оценки мы используем новую технику приближения булевых функций, которую впервые применил Шерстов [Sherstov, 2020]. Также мы доказываем, что если нас интересуют только входы, ограниченные по весу параметром k, то оценку можно значительно улучшить, выразив разрешающий список ППФ степени O(sqrt(k)) и веса n^O(sqrt(k)), и доказываем соответствующую нижнюю оценку.
Видеозапись семинара.

23.11.2022 Мария Тихонова "Трансформерные модели в языковом моделирование"
Доклад посвящен современным подходам языкового моделирования в области автоматической обработки текстов (Natural Language Processing). На докладе будет рассмотрена архитектура трансформер и механизм внимания (attention mechanism), на которых на сегодняшний день основано большинство нейросетевых языковых моделей.
Видеозапись семинара

19.10.2022 Федор Куянов "Теоретико-числовые свойства волновой функции в модели "Шашки Фейнмана""

Этот доклад посвящён шашкам Фейнмана -- элементарной модели движения электрона, предложенной Р. Фейнманом. В этой модели шашка движется по простым правилам по клетчатой доске, а мы следим за её поворотами. Шашки Фейнмана также известны как одномерное квантовое блуждание. Доказываются новые теоретико-числовые результаты в этой модели, например, чередование знаков вещественной и мнимой части волновой функции электрона на определённом интервале. Для этого использовалось полученное недавно рекуррентное соотношение. Также при помощи асимптотической формулы исследуются положения провалов у вещественной части волновой функции электрона. Все эти результаты формулируются также на языке диаграмм Юнга.

15.09.2022 Иван Михайлин (ММИ имени Леонарда Эйлера) Доклад по статье "A better-than-3logn depth lower bound for De Morgan formulas with restrictions on top gates" опубликованной на CCC2022.
В докладе будет рассказано о сложности композиций функций, а именно будет доказано что для случайной функции f и любой a<0.2 существует функция g, такая что ксор-композиция f и g не вычисляется дизъюнкцией2^{2 a n} формул размера 2^{(1-a)n}. В качестве основного технического ингредиента будет доказано что случайное множество функций является достаточно перемешенным (в том смысле что в нем нет "комочков" - подмножеств функций похожих друг на друга), даже после композиции со случайной функцией. Для этого будет использована лемма доказанная Кавой Хусейни, о пересечении линейно независимых сдвигов случайного подмножества F_2^n.
Видеозапись семинара.

21.04.2022 Юрий Малыхин (МИАН) "Сложность матриц и аппроксимация"
Мы рассмотрим различные меры сложности матриц и тензоров: аппроксимативный ранг, сигнум-ранг, жёсткость.
Обсудим применение этих понятий и соответствующих методов в классических задачах теории приближений - оценке n-членных приближений и колмогоровских поперечников.

17.03.2022 Андрей Игнатов "Fitting Protein into H-Core: Structural Analysis of Discrete Hydrophobic Cores" 
Protein folding is a process by which a protein chain acquires its native 3-dimensional structure (named conformation). Modeling the whole folding process is a challenging problem as it includes a huge number of degrees of freedom.
One possible approach to relieve this issue is using coarse-grained protein models. They simplify the protein geometry by merging several groups of atoms into one unified atom. The current research is about HP-models where the whole amino acid residues are represented by unified atoms. These atoms can be of two types – H (hydrophobic), or P (polar). Hydrophobic residues are known to be present inside the protein molecule, while polar ones can stay on its surface.
In HP-model, monomers (unified residues) can be present only in nodes of some lattice. This turns the problem of protein folding into a discrete optimization problem where the number of H-H contacts needs to be maximized. This problem can be solved by creating the maximally dense H-Core (hydrophobic core with the maximal number of H-H contacts) and fitting the protein into it.
In the report, several methods of speeding up 2D H-Core construction and the following protein fitting are going to be presented. Additionally, some recent advances in 3D H-Core construction are going to be reported.
Development of this theory may help in rapid creation of a first approximation of the protein structure.

24.02.2022 Павел Захаров "Evolution of a bipartite random graph"
The evolution is a topic concerning the distribution of components' sizes and their number in random graph. Most of the facts are known when the basic graph is a so-called spectral expander (for instance well-known G(n, p), where the basic graph is K_n). We are going to extend some facts on the bipartite random graph model G(n, n, p). The main result is the proof of the central limit theorem for the number of vertices in the giant component for p = c/n, c > 1.
Видеозапись семинара.

17.02.2022 Anand Mahendran "On the Generative Power of Semi-Bracketed Contextual Grammars"
Bracketed and fully bracketed contextual grammars were introduced in 1998 to bring the notion of a tree structure to the strings generated by the grammar. The tree structure was defined by choosing the selectors of minimally Dyck covered strings and by associating a pair of parentheses to the adjoining contexts in the derivation. However, these grammars failed to generate the three basic non context-free languages that are required for representing natural languages. To overcome this failure, a model namely Semi-bracketed contextual grammar was introduced and the generative power of the grammar has been studied a little. In this work, we discuss the generative power of Semi-bracketed contextual grammars and relate the results with the Chomsky family of languages and the languages generated by internal contextual grammars under maximal local, maximal global and left most derivation mode. We also discuss various closure properties of the family of languages generated by Semi-bracketed contextual grammars with finite and regular choice.
Видеозапись семинара

10.02.2022 Libor Barto (Charles University) "The number of homomorphisms into finite algebras"
In a recent joint work with William DeMeo and Antoine Mottet, we have characterized finite algebras A such that the number of homomorphism from any finite algebra X into A is bounded by a polynomial in the size of X. I will talk about this result, discuss its motivation and background, give examples, and mention open problems.
Видеозапись семинара.

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

27.01.2022 Александр Смаль (ПОМИ РАН) "Формульная сложность и гипотеза Карчмера - Раза - Вигдерсона"
Одна из основных открытых задач формульной сложности - это доказательство суперкубической оценки на размер формулы для явной булевой функции. Наилучшая известная оценка такого вида - это кубическая оценка Хостада для функции Андреева, которая была получена более 20 лет назад. Один из возможных подходов к этой задаче - это реализация программы, предложенной Карчмером, Разом и Вигдерсоном, которая потенциально может привести в доказательству суперполиномиальной нижней оценки для функции из класса P, из чего будет следовать разделение сложностных классов P и NC1. 
На семинаре мы поговорим про эту программу, заключающуюся в доказательстве гипотезы Карчмера - Раза - Вигдерсона, и обсудим, каких успехов удалось добиться на этом пути.
Видеозапись семинара.

13.01.2022, 20.01.2022 Александр Козачинский "Разрешимость в позиционных стратегиях - в поисках полного описания"
В области игр на графах особый интерес вызывают выигрышные условия (и, более общо, платежные функции), разрешимые в позиционных стратегиях. Эти условия находят применения в логике (разрешимость логических теорий, модальное mu-исчисление), а также в более практических областях (верификация программ, реактивное программирование). Хотелось бы понять, как вообще могут быть устроены такие выигрышные условия и платежные функции. Классическим результатом в этой области является теорема Жимбера и Желонки (2005) - если платежная функция разрешима в позиционных стратегиях в играх с одним игроком, то и в играх с двумя игроками. Эта теорема значительно упрощает доказательства разрешимости в позиционных стратегиях для конкретных платежных функций. К сожалению, она не дает явного описания всех таких платежных функций. Кажется возможным получить явное описание для платежных функций, удовлетворяющих некоторым дополнительным условиям. Это было сделано мной для непрерывных платежных функций (CONCUR 2021). Непрерывность представляется естественным дополнительным условием, поскольку ему удовлетворяет один из классических примеров позиционной платежной функции - discounted sum payoff. Другим естественным дополнительным условиям представляется префиксная независимость (при удалении любого конечного префикса значение платежной функции не меняется). Классическими примерами с этим условием являются игры четности и циклические игры. Явного описания для этого случая пока не получено, но есть гипотеза, что все такие платежные функции можно получить как циклические игры на упорядоченных группах. В докладе будет предложено рассказать о каком-нибудь из этих результатов.

19.05.21 А. Стороженко (UCLA) "An Optimal Separation of Randomized and Quantum Query Complexity"
Understanding the relative power of quantum and classical computing is of basic importance in theoretical computer science. In this talk, I will discuss an optimal separation of quantum and randomized complexities in the query model.

First, we show the upper bound on the sum of the absolute values of the Fourier coefficients of given order $\ell$ for an arbitrary decision tree. The bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). This result is of interest in its own right, independent of its use to obtain optimal quantum-classical separations.
As an application, we obtain, for any positive integer $k$, a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $k/2$ and randomized query complexity $\Omega(n^{1-1/k})$ (up to polylogarithmic factors). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015). Prior to our work, the best known separation was polynomially weaker: $O(1)$ versus $n^{2/3-\epsilon}$ for any $\epsilon>0$ (Tal, FOCS 2020).

14.04.21
А. Бычков "Optimal monomial quadratization for ODE systems"
Abstract: Consider a system of ODEs with polynomial right-hand side, for example, a scalar ODE: $x’ = x^5$. Introducing a new variable $y = x^4$ leads us to a system of two equations: $x’ = xy$ and $y’ = 4x^3 x’ = 4x^4 y = 4y^2$. The right-hand sides of the new system are of degree at most two, and every solution of the original system is the x-component of some solution of the new system. Such problem, given a system of ordinary differential equations (ODEs) with polynomial right-hand side, transform it into a system with quadratic right-hand side, is called a quadratization problem. The quadratization problem has emerged recently in such areas as model order reduction, numerical solutions of ODEs and chemical reaction networks. In 2011, Ch. Gu proved that it is always possible to perform quadratization with new variables being monomials in the original variables (like $x^4$ in the example above). We call such quadratization monomial. Later in 2020, M. Hemery, F. Fages, and S. Soliman, have showed that the problem of finding an optimal (i.e. of the smallest possible dimension) monomial quadratization is NP-hard. They also designed and implemented an algorithm for finding a monomial quadratization which is practical and yields an optimal monomial quadratization in many cases. In the talk, I will show the results of our recent preprint with G. Pogudin, in which we designed and implemented a practical algorithm that is guaranteed to find an optimal monomial quadratization. We will also discuss encoding the optimal monomial quadratization problem as APX-hard [2]-sumset cover problem. 

10.03.21
M. Anand "Studies on Insertion-deletion Systems and Contextual Grammars Related to Ambiguity, Measures and Applications"
Gene insertion and deletion are the operations that occur commonly in Deoxyribonucleic acid (DNA) processing and Ribonucleic acid (RNA) editing. Based on these operations, a computing model has been formulated in formal language theory known as insertion-deletion systems. As the biological macromolecules can be viewed as symbols, the gene sequences can be represented as strings.
This suggests that the molecular representation can be theoretically analyzed if a biologically inspired computing model recognizes various bio-molecular structures that are predominantly available in DNA, RNA and proteins. Contextual grammars were introduced by Solomon Marcus in 1969 (Marcus 1969), based on the fundamental concept of descriptive linguistics. Internal contextual grammars were introduced by Păun and Nguyen in 1980 as a variant of contextual grammars. Several descriptional complexity measures and various levels of ambiguity were defined for (internal) contextual grammars. Bracketed and Fully bracketed contextual grammars were introduced (Martín Vide and Păun (1998)) to bring the notion of a tree structure to the derived strings. Contextual grammars are the counterpart of insertion-deletion systems as ‘strings’ of latter are ‘selectors’ of former.
We introduce a simple grammar model called Matrix insertion-deletion system to encompass various bio-molecular structures that occur at intramolecular level like hairpin, stem and loop, cloverleaf and at intermolecular level such as double strand, nick language and holliday structure and basic RNA secondary structures like kissing hairpin, bulge loop, internal loop.
Based on the components used in the derivation, six new levels of ambiguity for insertion-deletion systems were introduced. We show that there are inherently i-ambiguous insertion-deletion languages which are j-unambiguous for the combinations (i, j) ∈ {(5, 4), (4, 3), (4, 2), (3, 1), (2, 1), (1, 0), (0, 1)}. Then, six new descriptional complexity measures for insertion-deletion systems based on the used contexts and strings were introduced. Finally, the trade-off between the ambiguity levels and various descriptional complexity measures were analyzed by introducing a new notion ‘pseudo inherently ambiguous languages’.
In addition to the work carried out in the domain of insertion-deletion system we carry out some work on its counterpart domain contextual grammar also. We analyze the trade-off between the ambiguity and descriptional complexity measures of languages generated by internal contextual grammars.

24.02.21
Н. Проскурин "О разрыве между степенью булевой функции и блочной чувствительностью"
В докладе рассматривается соотношение между двумя мерами сложности булевых функций: степенью многочлена $d(f)$, выражающего функцию над полем вещественных чисел, и блочной чувствительностью $bs(f)$. Мы улучшаем текущую оценку $ d^2(f) \geq bs(f) $, установленную Талом, до $ d^2(f) \geq (\sqrt{10} - 2)bs(f) $. Как следствие, мы также улучшаем оценки для некоторых других пар мер сложности. Например, мы улучшаем мультипликативную константу в недавнем результате из доказательства гипотезы чувствительности.
В следующем результате мы получаем похожее продвижение для разрыва между блочной чувствительностью и степенью приближающего многочлена $\deg_{1/3}^2(f)$: мы доказываем, что $\deg_{1/3}^2(f) \geq \sqrt{6/101} bs(f)$ и тем самым улучшаем предыдущую оценку $ \deg_{1/3}(f) \geq \sqrt{bs(f)/6} $, доказанную Нисаном и Сегери. В дополнение мы также строим пример, который показывает, что разница между константами в нижних и верхних оценках на степень не превосходит $0.2$.
В последнем результате мы изучаем свойства гипотетической полностью чувствительной в нуле функции от 10 переменных степени 4. Существование такой функции усилило бы разрыв между чувствительностью и степенью булевой функции. Мы доказываем, что в результате симметризации такой функции может получиться единственный многочлен, и явно приводим его формулу.
Видеозапись семинара

03.06.20 
Д. Жук "On the Complexity of the Surjective Constraint Satisfaction Problem"
Constraint Satisfaction Problem (CSP) is the problem of deciding whether there exists an assignment to a set of variables subject to some specified constraints. Surjective Constraint Satisfaction Problem (SCSP) is the variant of CSP where we require the solution to be surjective that is all values from the domain appear in the solution. Unlike the CSP, where the complexity was classified for all constraint languages, the complexity of the SCSP remains unknown even for very simple constraint languages.
In the talk we will discuss recent results of the author on the complexity of the SCSP. First, I proved NP-Hardness for one of the most popular constraint languages with unknown complexity (so called No-Rainbow Problem). Additionally, I found a counter-example to a widely-believed conjecture describing the complexity of the SCSP for all constraint languages.
Видеозапись семинара

20.05.20
Bruno Loff "NP-Hardness of Circuit Minimization for Multi-Output Functions"
I will show that it is NP-hard to compute the minimum circuit size of a given multi-output Boolean function f: {0,1}^n -> {0,1}^m. This result appears in a recent paper of ours, which will be presented at CCC 2020: https://eccc.weizmann.ac.il/report/2020/021/. I will also briefly overview the background behind this result and some other results from our paper. This is joint work with Rahul Ilango and Igor Oliveira.
Видеозапись семинара

22.04.20
В. Подольский "Вычисление функций голосования монотонными формулами маленькой глубины"
Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.
Доклад основан на совместной работе с Александром Козачинским: https://eccc.weizmann.ac.il/report/2020/017/
Видеозапись семинара.

01.04.20
А. Милованов "Предсказание битов бесконечной двоичной последовательности по ее префиксам"
Некоторое устройство выдаёт биты бесконечной двоичной последовательности согласно некоторому неизвестному вычислимому распределению вероятностей P. Задача предсказателя: угадать по первым n битам последовательности вероятность того, что следующим битом будет 0 (для всех n). Соломонов предложил использовать для этого универсальную (априорную) перечислимую снизу полумеру m, выдавая на префиксе x условную априорную вероятность появления 0 после  x. Мы предлагаем более естественное с интуитивной точки зрения решение: предсказатель находит распределение вероятностей Q небольшой сложности, относительно которого вероятность x достаточно близка к априорной вероятности, это распределение и будет использовано для предсказания. В докладе будет проведено сравнение нового предсказателся с предсказателем Соломонова.

04.03.20
А.Б. Скопенков "Алгоритмическая нераспознаваемость вложимости гиперграфов в евклидово пространство для коразмерности более 1."
Для коразмерностей 1 и 0 указанная в названии нераспознаваемость  несложно вытекает из теоремы Новикова о нераспознаваемости N-мерной сферы для N>4 (это показали Matousek, Tancer, Wagner, arXiv:0807.0336 [cs.CG]).
Я расскажу о соответствующем результате для коразмерности 2 и более, который  анонсирован в 2019 (Filakovsky, Wagner, Zhechev). Его красивое доказательство использует алгоритмическую нераспознаваемость продолжаемости отображений (Cadek, Krcal, Matousek, Vokrinek, Wagner, arXiv:1302.2370 [cs.CG]).  Я расскажу и о выводе последней нераспознаваемости из нераспознаваемости разрешимости диофантовых уравнений. 

15.01.20
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.

18.12.19
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.

27.11.19
Илья Воробьев (Сколтех) " 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.

20.11.19
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.

13.11.19
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*.

 25.09.19
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.

18.09.19
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

11.09.19
Вадим Гринберг (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.

04.09.19
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.)

21.08.19
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.

21.08.19
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.

19.06.2019
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).

07.06.2019
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.

05.06.2019
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.

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

17.04.2019
В. Подольский "Балансирующие семейства множеств и пороговые схемы глубины 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/

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

 

03.04.2019
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.

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

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

06.03.2019
А. Милованов "Игры на машинах Тьюринга и сила случайных строк"
В статье [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-полной. Это результат показывает, что для нахождения лучших верхних границ для упомянутых классов требуются новые методы.

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

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

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

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

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

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

14.11.2018
В. Гурвич "Функции Шпрага-Гранди (ШГ) игры НИМ на гиперграфе"
Мы рассматриваем следующее, весьма широкое, обобщение игры НИМ.
Имеется $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$. При этом функция ШГ задаётся в точности функцией Дженкинса и Майберри для НИМ Мура, только одна из переменных определяется "немного" по-другому.
Оказывается, это не случайное совпадение. Мы нашли очень широкий класс гиперграфов, для которых функция ШГ даётся формулой Дженкинса и Майберри.

07.11.2018
А. Чистопольская "Глубина разрешающих деревьев с 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. Также я расскажу пример функции, для которой эта нижняя оценка не является точной.

10.10.2018
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.

03.10.2018
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.

26.09.2018
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.

19.09.2018
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.

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

20.06.2018
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.

13.06.2018 
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.

30.05.2018
Г. Евстропов "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).

23.05.2018
Г. Пособин "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).

16.05.2018
А. Ромащенко "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.

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

04.04.2018
Ю. Нестеров "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.

21.03.2018
А. Милованов "Дерандомизация 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.

07.03.2018
А. Рубцов "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.

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

07.02.2018
В. Подольский "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).

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

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

13.12.2017
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.

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