Laboratory of Mathematical Logic at PDMI

Вторник, 19 октября, комната 106. Начало в 18:00.

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

Вторник, 12 октября, комната 106. Начало в 18:00.

12 октября.
Э.Гирш. Доклад о новых результатах о выполнимости (независимый, но непересекающийся с докладом в понедельник).
Точный круг вопросов будет определен по результатам обсуждения доклада в понедельник, но во всяком случае в доклад войдут результаты, касающиеся "фазового перехода" для выполнимости. Кратко, тематика такова: для 2-выполнимости известно, что если в формуле соотношение кол-ва дизъюнкций и переменных < 1, то формула почти наверняка выполнима, а если > 1, то почти наверняка невыполнима. Уже для 3-выполнимости точная оценка неизвестна, из компьютерных экспериментов предполагается, что граничное соотношение должно быть около 4.25. Будут рассказаны какие-либо из оценок этого соотношения сверху и/или снизу (в преддверии надвигающегося доклада Д.В.Карпова о похожем результате для 3-раскрашиваемости.)

Четверг, 7 октября, комната 106. Начало в 18:00.

7 октября.
Д.В.Карпов "Экстремальные графы без K_{2,n} и без K_{3,3}. Cерии примеров."
Абстракт. Будет построена серия примеров графов без K_{3,3} из работы W.G. Brown. "On graphs that do not contain a Thomsen graph." (Canad. Math. Bull, Vol.9, No.3 (1966), p.281-285). В графах из этой серии количество ребер имеет тот же порядок, что и в доказанной в предыдущем докладе оценке сверху.
Также будут построены две серии примеров графов, не содержащих подграф (для фиксированного натурального ), взятые из неопубликованной работы Д.Карпова и С. Берлова "О наибольшем количестве ребер в графе, не содержащем K_{2,n}. Одна серия построена с помощью линейных отображений на проективной плоскости над полем F_p, a другая серия -- на основе двумерного векторного пространства над полем F_{p^\phi(n)}. C помощью этих примеров будет доказано, что при натуральном n, ex(V,K_{2,n+1})= 0.5*n^0.5*V^1.5 + o(V^{4/3}).

Вторник, 28 сентября, комната 106. Начало в 18:00.

28 сентября.
В.П.Оревков "Обратный метод для скулемовского случая"
АБСТРАКТ
В докладе будет изложен обратный метод поиска вывода для формул в скулемовской нормальной форме (формула находится в скулемовской нормальной форме, если она находится в предваренной форме и в префиксе кванторы существования не следуют за кванторами всеобщности). Будет также доказана разрешимость некоторых классов исчисления предикатов.

Понедельник, 20 сентября, комната 106. Начало в 18:00.

20 сентября.
Б.Ю.Конев прореферирует статью Владимира Лифшица
``What is the inverse method?''.
Будет рассказано о предложенном С.Ю.Масловым методе автоматического поиска вывода для исчисления предикатов первого порядка. Изложение будет расширено материалом из дополнения А к книге Ч. Чень, Р. Ли ``Математическая логика и автоматическое доказательство теорем'', авторы С.Ю.Маслов и Г.Е.Минц.

Пятница, 21 мая, комната 106. Начало в 18:00.

21 мая.
Э.Гирш. Доклад по статье Impagliazzo, Paturi, Zane "Which Problems Have Strongly Exponential Complexity?"
Доклад посвящен вопросу "можно ли решить NP-полную задачу за время 2^{epsilon n}" (для произвольного малого epsilon). Вводятся специальные редукции и с помощью результатов о полноте относительно этих редукций доказывается, что вопрос этот одинаково решается для многих задач (k-выполнимость, k-раскрашиваемость, клика...) Основная лемма -- такая редукция k-выполнимости с параметром "кол-во переменных" к k-выполнимости с параметром "кол-во дизъюнкций" (именно в эту сторону).
Имеется также несколько побочных результатов, но нет гарантии, что на них хватит времени в полном объеме.
---
Keywords: NP-complete problems, SAT, time complexity, Boolean circuits, pseudorandom generators.
Abstract. For several NP-complete problems (SAT, k-SAT, 3-Coloring), there have been a progression of better but still exponential algorithms (e.g., 3-SAT: 2^N, 1.8^N, 1.62^N, 1.57^N, 1.49^N, 1.37^N...). An intriguing question is whether for each positive epsilon there is a 2^{epsilon N}-time algorithm for each of these problems (*). The authors introduce a generalized reduction SERF which preserves sub-exponential complexity. One of the consequences of the results of the paper is that (*) is equivalent for k-SAT, k-Colorability, k-Set Cover, Independent Set, Clique, Vertex Cover (these problems are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal).
The main technical lemma is an algorithm that, for any positive epsilon, represents an arbitrary k-CNF formula as a disjunction of 2^{epsilon n} k-CNF formulas of linear size (i.e., each consists of O(n) clauses).
By-products. 1. With high probability, degree 2 random GF(2) polynomials require strongly exponential size for \Sigma^3_k circuits for k=o(log log n). 2. Thus there is a pseudorandom generator with O(n^2) bits of advice that maps n bits into a large number of bits so that computing parity is hard for that curcuits.

Пятница, 14 мая, комната 106. Начало в 18:00.

14 мая.
Продолжение доклада М.Всемирнова "Теоретико-числовые основы криптографии" (не особенно зависимое от предыдущей лекции, на которой была рассказана преимущественно история).
Будет рассказано об асимметричных систем кодирования, известных также как криптосистемы открытого ключа. Одним из применений таких систем является реализация электронных подписей.
В качестве примеров будут рассмотрены криптосистемы Меркле-Хеллмана (1978), основанная на проблеме рюкзака, и Ривеста-Шамира-Адлемана (1978).

Пятница, 30 апреля, комната 106. Начало в 18:00.

30 апреля.
М.Всемирнов "Теоретико-числовые аспекты криптографии".
Предполагается, что в докладе будет дан исторический обзор теоретико-числовых методов, применяющихся в криптографии. Особое внимание будет уделено системам криптографии с открытым ключом (public key cryptography, в частности, метод RSA).
Есть надежда, что этот доклад будет первым в серии "криптографических" докладов на нашем мини-семинаре.

Пятница, 16 апреля, комната 106. Начало в 18:00.

16 апреля.
В.Гребинский. Доклад, продолжающий цикл докладов о сложности по Колмогорову. В докладе будут рассмотрены дальнейшие свойства сложности по Колмогорову, а также их применение для получения нижних оценок сложности вычислений.

Пятница, 9 апреля, комната 106. Начало в 18:00.

9 апреля.
Д.Карпов "Классические вопросы, связанные с раскраской графов". В докладе будут освещены классические результаты о правильных раскрасках вершин графов в несколько цветов и состояние дел в этой области.