Laboratory of Mathematical Logic at PDMI

Пятница, 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
Задача выпуклого программирования --- это задача минимизации выпуклой функции на выпуклом теле. Для того, чтобы решить ее, необязательно знать задание этого тела в виде неравенств , где -- выпуклые функции. Я расскажу, что необходимо для решения таких задач за полиномиальное время. Также будет показано, что этим методом можно решать задачи полуопределенного программирования. Если останется время, то будут затронуты и приложения.

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

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

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

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

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

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

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

4 февраля.
В.Гребинский. Дискретная томография: реконструкция выпуклых многоугольников по ортогональным проекциям.
По мотивам статьи Marek Chrobak and Christoph Durr "Reconstructing hv-Convex Polyominoes from Orthogonal Projections".
Abstract
Дискретная томография изучает вопрос о реконструкции объекта по его "проекциям". Допустим, исследуемый объект задан в виде многомерного массива из 0 и 1. Можно ли восстановить этот объект исходя из сумм чисел по столбцам и строкам ? Для многих классов объектов, эта проблема NP-complete, но мы остановимся на интересном случае выпуклых множеств, когда она имеет эффективное решение.
References: Christoph Durr, Marek Chrobak: Reconstructing hv-Convex Polyminoes from Orthogonal Projections, Information Processing Letters, 69, 1999, 283-289.

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

28 января.
Э.Гирш. Доклад по статье M.Molloy, B.Reed "Further Algorithmic Aspects of the Local Lemma" (кажется, из STOC-98).
Доклад начнется с формулировок и примера применения Lovasz Local Lemma для "frugal" раскрасок графов, так что содержание доклада будет понятно всем (а не только тем, кто присутствовал на докладе В.Гребинского). Далее будет рассказано, как в некоторых случаях можно за полиномиальное время находить объекты, существование которых гарантирует эта Lemma.
ABSTRACT of that paper: We provide a method to produce an efficient algorithm to find an object whose existence is guaranteed by the Lovasz Local Lemma. We feel that this method will apply to the vast majority of applications of the Local Lemma, unless the application has one of four problematic traits. However, proving that the method applies to a particular application may require proving two (possibly difficult) concentration-like properties.

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

Докладчик: М. А. Всемирнов.

ВВЕДЕНИЕ В ТЕОРИЮ КОДОВ.
Доклад представляет собой обзор классических результатов в теории кодов. В частности, будет расказано о наиболее известных кодах и об их применении. Доклад основан на 3 главе книги Конвея и Слоана "Упаковки сфер, решетки и группы."

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

22 января.
Со-докладчики: Э.Гирш, В.Гребинский. Обсуждение статьи
Adam R. Klivans, Dieter van Melkebeek Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses. (ECCC TR 1998-075)
В этой статье, в частности, имеются некоторые результаты по дерандомизации Arthur-Merlin proofs.
Если останется время, можем обcудить содержание будущего доклада об алгоритмизации Lovasz Local Lemma.