Mathematical Logic and Discrete Mathematics at PDMI

Понедельник, 2 декабря, комната 203. Начало в 14:30.

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

Доклад по статье E.Balas, S.Ceria, G.Cornuejols
A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS
Abstract _статьи_:
We propose a cutting plane algorithm for mixed 0-1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovasz and Schrijver and the hierarchy of relaxations of Sherali and Adams.

Пятница, 29 ноября, комната 106. Начало в 16:30.

Докладчик: В. П. Оревков.

СТАРЫЕ и НОВЫЕ МЕТОДЫ АВТОМАТИЧЕСКОГО ПОИСКА ДОКАЗАТЕЛЬСТВ (продолжение)
Будет описано дерево поиска опровергающих моделей.

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

Докладчик: В. П. Оревков.

СТАРЫЕ и НОВЫЕ МЕТОДЫ АВТОМАТИЧЕСКОГО ПОИСКА ДОКАЗАТЕЛЬСТВ (цикл лекций)
Основное внимание в первой лекции будет уделено разрешимости теории вещественных чисел и теории сложения натуральных чисел.
В дальнейшем будут рассмотрены:
1. Генценовские секвенциальные исчисления. 2. Метод резолюций. 3. Обратный метод.
Будут описаны новые тактики поиска доказательств как для метода резолюций, так и для обратного метода.

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

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

VISUAL CRYPTOGRAPHY SCHEMES или КРИПТОГРАФИЯ ПО ФАКСУ
(по статье G. Ateniese, C. Blundo, A. de Santis, and D. R. Stinson "Constructions and Bounds for Visual Cryptography").
Пусть у нас есть множество P из n людей. Некоторые подмножества P являются уполномоченными, причем любое надмножество уполномоченного тоже уполномочено. Тогда VCS - это метод закодировать секретное изображение с помощью n "черно-прозрачных" картинок и разослать их нашим n участникам так, что выполнено два свойства:
1) любое уполномоченное множество людей из этих n сможет расшифровать исходное изображение просто сложив полученные картинки в стопку (т.е. применить к составляющим ее битам операцию OR), и
2) по картинкам, которые получили люди из не уполномоченного набора будет абсолютно невозможно восстановить исходный секрет.
В докладе будет рассказана реализация этого метода.

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

Докладчик: А. Бовыкин.

БЛЕСТЯЩИЕ МОДЕЛИ (ПОЛУЧАЮЩИЕСЯ ИЗ АРИФМЕТИЗОВАННОЙ ТЕОРЕМЫ О ПОЛНОТЕ)
(продолжение)
Доклад будет посвящен "блестящим" моделям теории первого порядка. Модель M теории T в языке L называется блестящей, если ее можно расширить до модели любого утверждения F в языке L\cup\{R_1,...,R_n\} с параметрами \vec{a} из M, совместного с Th(M,\vec{a}). Слушателям покажут блестящие плотные порядки, блестящие случайные графы и другие блестящие структуры.
Предыдущий доклад (18 октября) был посвящен введению в теорию моделей.

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

Докладчик: А. Бовыкин.

БЛЕСТЯЩИЕ МОДЕЛИ (ПОЛУЧАЮЩИЕСЯ ИЗ АРИФМЕТИЗОВАННОЙ ТЕОРЕМЫ О ПОЛНОТЕ)
Первый из двух докладов будет посвящен введению в классическую теорию моделей, модели арифметики и арифметизованную теорему о полноте. Будет приведено множество примеров теорий и моделей теорий, а также крайзелевское доказательство второй теоремы Геделя.
Продолжение планируется на 25 октября. Второй доклад будет посвящен "блестящим" моделям теорий первого порядка. Модель M теории T в языке L называется блестящей, если ее можно расширить до модели любого утверждения F в языке L\cup\{R_1,...,R_n\} с параметрами \vec{a} из M, совместного с Th(M,\vec{a}). Слушателям покажут блестящие плотные порядки, блестящие случайные графы и другие блестящие структуры.

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

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

Доклад по статье: M.Alekhnovich, E.Ben-Sasson
ANALYSIS OF THE RANDOM WALK ALGORITHM ON RANDOM 3-CNFS
(продолжение)

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

Докладчик: Д. В. Карпов.

БЛОКИ В K-СВЯЗНОМ ГРАФЕ
Структура блоков и точек сочленения для связных графов хорошо известна и достаточно полезна. Разбиение связного графа на блоки помогает изучать структуру связного графа. Понятие вершинной k-связности можно рассматривать как обобщение понятия связности. Это позволяет предположить, что обобщения блочной структуры связного графа до разбиения k-связного графа на (k+1)-связные блоки может представлять интерес для исследования структуры k-связных графов.
В различных работах делались попытки определить структуру разбиения графа на "многосвязные" блоки (например, D.W.Matula, k-Blocks and Ultrablocks in Graphs, J. Comb.Theory, Ser.B, vol.24 (1978), 1-13; W.Hohberg, The decomposition of graphs into k-connected components, Discr. Math., vol.109 (1992), 133-145; Д.Карпов, А.Пастор, О структуре k-связного графа, Записки научных семинаров ПОМИ, т.266 (2000), 76-106).
В докладе будет рассмотрен новый подход к этой проблеме, развивающий идеи работы Д.Карпова и А.Пастора.

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

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

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

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

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

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