DM Seminar

Discrete Mathematics Seminar

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

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

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

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

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

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

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

Syndicate content