DM Seminar

Discrete Mathematics Seminar

Семинар 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 и описаны некоторые вопросы, возникающие в связи с этим понятием.

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

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

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

Семинар 26 февраля 1999 года

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

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

Семинар 18 февраля 1999 года

Четверг, 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 февраля 1999 года

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

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

Syndicate content