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

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

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

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
В. Чернышев "Динамика точек на метрических графах"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В докладе планируется коротко рассказать о некоторых работах прошедшей недавно конференции STACS 2017.
В основном планируется рассказать о тех статьях, в которых видна возможность для дальнейших продвижений.
Тексты всех работ
 
15.03.2017 г. - 22.03.2017 г.
М. Вялый "Тонкие сводимости"

Неформально говоря, сильная гипотеза об экспоненциальном времени (SETH) утверждает, что самый быстрый способ решить задачу выполнимости (k-SAT) - это вычислить значение КНФ во всех точках. Эта гипотеза настолько сильна, что имеет все шансы оказаться ложной.
В попытках опровержения SETH возникла интересная техника тонких сводимостей (fine-grained reductions). С помощью этой техники можно связывать гипотезы об оптимальном времени решения задач, имеющих очень разную сложность - от экспоненциальной до квадратичной.
В докладе будут даны точные формулировки SETH и fine-grained reductions, приведены простые примеры тонких сводимостей. Кроме того, обсудим, какую роль в этой технике играет лемма о похудании (sparsification lemma).
 
09.03.2017 г.
А. Кноп "Теоремы об иерархии по времени для эвристических вычислений"

В докладе мы обсудим то, что для вероятностных вычислений теоремы об иерархиях по времени все еще не известны, но можно доказывать их, если перейти от сложности в худшем случае, к сложности в среднем.
 
22.02.2017 г. - 03.03.2017 г.
Г. Евстропов "Оптимальные алгоритмы решения некоторых антагонистических игр с упорядоченными множествами монет"

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


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

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

Игры четности - важный класс бесконечных игр на графах, интересный и с теоретической точки зрения, и с точки зрения приложений. Решение игр  четности как алгоритмическая задача лежит в пересечении классов NP и  coNP. Полиномиальных алгоритмов решения игр четности неизвестно. Уже  довольно давно были получены субэкспоненциальные алгоритмы решения игр  четности.
Осенью 2016 года был достигнут неожиданный успех: C.S. Calude, S. Jain,  B. Khoussainov, Wei Li, F. Stephan нашли квазиполиномиальный алгоритм  решения игр четности (Квазиполиномиальный означает экспоненту от  степени логарифма.) Результат получается остроумной сводимостью игр  четности к обычным позиционным играм на ациклическом графе  квазиполиномиального размера. Рассуждения совершенно элементарные, хотя  и  технически громоздкие.
В докладе будет изложен этот алгоритм.
 
11 .01.2017 г.
Tomislav 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 и отправьте нам уведомление. Спасибо за участие!