Latest seminars

Семинар 7 октября 1999 года

Четверг, 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} $ (для фиксированного натурального $ n $), взятые из неопубликованной работы Д.Карпова и С. Берлова "О наибольшем количестве ребер в графе, не содержащем 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 сентября 1999 года

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

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

Семинар 20 сентября 1999 года

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

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

Семинар 21 мая 1999 года

Пятница, 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 мая 1999 года

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

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

Семинар 30 апреля 1999 года

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

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

Семинар 16 апреля 1999 года

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

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

Семинар 9 апреля 1999 года

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

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

Семинар 2 апреля 1999 года

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

2 апреля.
Продолжение (окончание) доклада А.Пастора "Kolmogorov Complexity: Recent Research in Moscow".

Семинар 26 марта 1999 года

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

26 марта.
А.Пастор расскажет кое-что о сложности по Колмогорову.
Доклад составлен на основе статьи В. А. Успенского "Kolmogorov Complexity: Recent Research in Moscow". В докладе будет освещена одна из разновидностей Kolmogorov Complexity -- так называемая simple Kolmogorov complexity и описаны некоторые вопросы, возникающие в связи с этим понятием.