Mathematical Logic and Discrete Mathematics at PDMI

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

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

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

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

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

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

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

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

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

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

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

5 марта.
М.Гаврилович и Э.Гирш расскажут о том, как дискретные оптимизационные задачи (например, MAX-SAT) трансформируются в задачи полуопределенного программирования, и как полученные задачи решаются (будет рассказан один из методов решения таких задач).

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

26 февраля.
М.Гаврилович. Доклад, освещающий, в том числе, метод решения задач популярного ныне полуопределенного программирования.
Abstract
Задача выпуклого программирования --- это задача минимизации выпуклой функции на выпуклом теле. Для того, чтобы решить ее, необязательно знать задание этого тела в виде неравенств $f_i\lt 0$, где $f_i$ -- выпуклые функции. Я расскажу, что необходимо для решения таких задач за полиномиальное время. Также будет показано, что этим методом можно решать задачи полуопределенного программирования. Если останется время, то будут затронуты и приложения.

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

18 февраля.
Б.Конев. Оракульные вычисления (источник -- книга Ch.Papadimitriou "Computational Complexity", раздел 14.3).
Abstract
Доклад будет посвящен оракульным вычислениям и возможности их применением к задаче установления равенства/неравентсва сложностных классов. Будет, в частности, показано, что существуют оракулы A и B, для которых 1) $P^A = NP^A$, 2) $P^B != NP^B$. Тем самым, будет показано, что знание уравнивающего или разделяющего оракула, вообще говоря, ничего не добавляет к знанию о равенстве/неравенстве сложностных классов.

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

15 февраля.
Докладчик -- М.Всемирнов, тема прежняя, содержание независимо от того, что было рассказано на прошлом заседании (на самом деле на прошлом заседании статья C.Pomerance не реферировалась).

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

12 февраля.
М.Всемирнов прореферирует статью C.Pomerance "Very short primality proofs".
В этой статье показано, что сертификацию любого простого числа можно осуществить всего за O(log p) умножений по модулю p. Поскольку предложенная техника использует арифметику эллиптических кривых над конечными полями, то часть доклада будет посвящена введению в эту область. Предварительных знаний от слушателей не требуется.