DM Seminar

Discrete Mathematics Seminar

Семинар 27 сентября 2002 года

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

Докладчик: Ю. Лифшиц.

ЗАДАЧА О ВИЗАНТИЙСКОМ СОГЛАШЕНИИ. ЕЕ ОТНОШЕНИЕ К СИСТЕМАМ НАДЕЖНОСТИ.
Формулировка: Есть n генералов, каждый из которых принял свое решение отступать или атаковать. Среди них t подкуплено, действия этих генералов непредсказуемы. Известно что 3t<n. Тогда можно создать такой протокол (одинаковый для всех генералов) пораундового обмена информацией так, чтобы 1) все генералы приняли итоговое решение, 2) все честные генералы принимают одинаковое решение, 3) это решение должно совпасть с исходным решением хотя бы одного честного генерала.
Задача поставлена в 1980 году, окончательно решена в 1998 в работе Гарая и Мозеса. Кроме того, в работе Фишера и др. доказана минимальность их алгоритма по количеству раундов (их необходимо t+1).

Семинар 24 сентября 2002 года

Вторник, 24 сентября, комната 412. Начало в 13:00.

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

Доклад по статье: M.Agrawal, N.Kayal, N.Saxena
PRIMES is in P (продолжение)

Семинар 20 сентября 2002 года

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

Докладчик: А. А. Кожевников.

Доклад по статье: M.Alekhnovich, E.Ben-Sasson
ANALYSIS OF THE RANDOM WALK ALGORITHM ON RANDOM 3-CNFS
В статье исследуется поведение простейшего алгоритма случайного блуждания на случайно порожденных формулах. В частности, доказывается верхняя полиномиальная оценка для случая формул с плотностью (=кол-во дизъюнкций/кол-во переменных) менее 1.63 и нижняя экспоненциальная оценка для случая с большой плотностью.

Семинар 6 сентября 2002 года

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

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

Доклад по статье: M.Agrawal, N.Kayal, N.Saxena
PRIMES is in P
В статье предлагается детерминированный полиномиальный по времени алгоритм, определяющий, является ли данное число простым.

Семинар 22 августа 2002 года

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

Докладчик: В. Крейнович (University of Texas at El Paso).

FUZZY LOGIC FROM THE MATHEMATICIAN'S VIEWPOINT: WHAT IS IT? WHAT ARE ITS MAIN RESULTS? MAIN SUCCESSES? MAIN PROBLEMS?
Fuzzy logic is a (successful) way to transform the expert's knowledge of the type "if the velocity is big and the distance from the object is small, hit the brakes and decelerate as fast as possible" into an actual control. To apply this transformation one must: 1) describe how to formalize words like "small", "big"; 2) choose operations corresponding to "and" and "or"; 3) choose a method that transforms the resulting fuzzy variable into a single value. The wrong choice can drastically affect the quality of the resulting control, so the problem of choosing the right procedure is very important. From mathematical viewpoint these choice problems correspond to non-linear optimization and are therefore extremely difficult. We describe how the corresponding optimization problem can be solved, what are the resulting choices, what logics they correspond to, and what are the remaining open problems.

Семинар 24 июня 2002 года

Понедельник, 24 июня, комната 203. Начало в 14:00.

Докладчик: Д. В. Пасечник (Франкфурт).

FINDING OPTIMUM SUBJECT TO FEW QUADRATIC CONSTRAINTS IN POLYNOMIAL TIME (joint work with D.Grigoriev i E. de Klerk)
It is shown that quadratic programming in $ n $ variables subject to $ k $ quadratic constraints has time complexity $ n^{O(k^2)} $, while feasibility can be tested in $ n^{O(k)} $ operations. The described procedure outputs the optimal value, as well as an optimal point, if they exist. Otherwise, it reports the range of the objective function on the feasible region. Optimal points and values are given exactly, via algebraic numbers. For this purpose the tools of quantifier elimination over the real closed fields with infinitesimals are involved.
In contrast, the best previously known procedure needs $ n^{O(k^2)} $ operations just for answering feasibility in the homogeneous case due to A.Barvinok, and no polynomial-time procedure previously known is able to find a feasible point with prescribed precision.

Семинар 21 июня 2002 года

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

Докладчик: А. Кожевников.

Доклад по статье P.Parrilo
ИСПОЛЬЗОВАНИЕ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ ДЛЯ ПОИСКА ПОЛУАЛГЕБРАИЧЕСКИХ ДОКАЗАТЕЛЬСТВ
Полуалгебраические системы доказательств -- один из новых интересных и активно изучаемых классов систем пропозициональных доказательств. В статье описывается новый подход для определения разрешимости системы полиномиальных неравенств с использованием полуопределенного программирования.
Основная идея метода заключается в переформулировке задачи разложения полинома от многих переменных в сумму квадратов в полуопределенную программу. Также используются некоторые результаты из вещественной алгебраической геометрии.
Автором статьи предложен эффективный алгоритм нахождения доказательства ограниченной степени в Positivstellensatz. Методы, использованные в этом алгоритме, имеют приложение и к другим задачам.
Источник: P.Parrilo, "Semidefinite programming relaxations for semialgebraic problems", Preprint, 2001, 15.

Семинар 18 июня 2002 года

Вторник, 18 июня, комната 412. Начало в 15:00.

Докладчик: Б. Ю. Конев.

СУБЪЕКТИВНЫЙ ВЗГЛЯД НА СИСТЕМЫ АВТОМАТИЧЕСКОГО ВЫВОДА ТЕОРЕМ

Семинар 11 июня 2002 года

Вторник, 11 июня, комната 106. Начало в 18:00.

Докладчик: А. О. Слисенко (Paris).

РАЗРЕШИМЫЕ КЛАССЫ В ЛОГИКЕ, ОСНОВАННЫЕ НА КОНЕЧНОЙ ОПРОВЕРЖИМОСТИ И ВЫПОЛНИМОСТИ

Семинар 26 апреля 2002 года

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

Докладчик: А. Кожевников.

Доклад по статье A.Atserias, M.Bonet
ОБ АВТОМАТИЗАЦИИ МЕТОДА РЕЗОЛЮЦИЙ И СВЯЗАННЫХ С НЕЙ СИСТЕМ ДОКАЗАТЕЛЬСТВ
(продолжение)

Syndicate content