Latest seminars

Семинар 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 не реферировалась).

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

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

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

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

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

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

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

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

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

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

Пятница, 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.

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

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

14 января 1999 года.
М.Гаврилович. Доклад об одном методе, имеющем непосредственное отношение к решению задач полуопределенного программирования (с помощью полуопределенного программирования в приближенно решаются многие дискретные задачи -- например, максимальное сечение графа, максимальная выполнимость булевой формулы).
Abstract
Я расскажу о методе Ньютона для оптимизации само-согласованных выпуклых функций на выпуклых областях---простейшем interior point method'е. Если останется время, я также постараюсь рассказать о применениях само-согласованных функций к некоторым задачам типа квадратичного программирования.

Семинар 30 декабря 1998 года

Cреда, 30 декабря, комната 106. Начало в 18:00.

30 декабря 1998 года.
В.Гребинский, "Lovasz Local Lemma".