DM Seminar

Discrete Mathematics Seminar

Семинар 2 марта 2001 года

Пятница, 2 марта, комната 412. Начало в 13:00.

Докладчик: О. Етеревский.

ЕЩЕ О ЧИСЛАХ КАРМАЙКЛА
В докладе улучшена оценка на число простых делителей строгого числа Кармайкла n-го порядка. Будет описан способ улучшения оценки для нестрогих чисел Кармайкла порядка n при малых n. Попутно доказывается оценка снизу на сумму $ \sum_{k=1}^n \phi(k) $.

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

Понедельник, 26 февраля, комната 412. Начало в 12:00.

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

ПРОДОЛЖЕНИЕ доклада
НИЖНИЕ ОЦЕНКИ ДЛЯ СИСТЕМ ФРЕГЕ С ОГРАНИЧЕННОЙ ГЛУБИНОЙ

Семинар 23 февраля 2001 года

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

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

НИЖНИЕ ОЦЕНКИ ДЛЯ СИСТЕМ ФРЕГЕ С ОГРАНИЧЕННОЙ ГЛУБИНОЙ
Состоится доклад по статье P.Beame, S.Riis "More on the relative strength of counting principles".
Будет доказана нижняя экспоненциальная оценка размера доказательства версии "на" принципа Дирихле (onto-PHP^{n+n^{\epsilon\log n}_n}) для систем Фреге с ограниченной глубиной (bounded-depth Frege) даже в случае, если в качестве схемы аксиом добавляются все "считающие" тавтологии Count_p (т.е. тавтологии, выражающие факт, что не существует совершенного разбиения множества из M элементов на блоки по p элементов, если M!=0 (mod p)).

Семинар 6 февраля 2001 года

Вторник, 6 февраля, комната 106. Начало в 11:59.

Докладчик: Э. Гирш.

ДОКАЗАТЕЛЬСТВО PCP THEOREM
Будет приведено доказательство первой (более простой) части PCP Theorem, иначе говоря, доказано, что для проверки выполнимости булевой формулы достаточно проверить всего лишь КОНСТАНТНОЕ количество битов "доказательства" (при этом разрешается использовать O(n^3) случайных битов).
Необходимые определения будут повторены (впрочем, они фактически содержатся в предыдущем абзаце).
Web-page семинара: http://logic.pdmi.ras.ru/~hirsch/minisem/ Подписка: email по адресу majordomo@logic.pdmi.ras.ru с командой SUBSCRIBE _minisem

Семинар 30 января 2001 года

Вторник, 30 января, комната 106. Начало в 12:00.

Докладчик: Э. Гирш.

ВЕРОЯТНОСТНО ПРОВЕРЯЕМЫЕ ДОКАЗАТЕЛЬСТВА (PCP THEOREM)
Первый в серии докладов об одном из наиболее значительных достижений в структурной теории сложности 1990-х годов, положительно отвечающем на вопрос
"МОЖНО ЛИ ПРОВЕРИТЬ ДОКАЗАТЕЛЬСТВО, ПРОЧТЯ В НЕМ ЛИШЬ ТРИ БИТА?"
(Речь идет о доказательствах утверждений, принадлежащих классу NP.)
Язык принадлежит классу PCP(r(n),q(n)), если доказательство принадлежности к нему может быть проверено с использованием O(r(n)) случайных битов и O(q(n)) битов доказательства. Так называемая PCP Theorem гласит, что
NP = PCP(log n,1),
т.е., например, для вероятностной проверки выполнимости булевой формулы достаточно знать лишь КОНСТАНТНОЕ число (на самом деле, 3) битов доказательства. (Заметим, что определение NP требует проверки ВСЕХ битов доказательства.)
Содержание первого доклада: 1. Определения. 2. Дискуссия. 3. Связь с нижними оценками для приближенных алгоритмов.

Семинар 16 января 2001 года

Вторник, 16 января, комната 106. Начало в 12:00.

Докладчик: А. В. Пастор.

РАНГ МАТРИЦ И СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ
Доклад представляет собой обзор статей B.Codenotti "Matrix rigidity" и B.Codenotti, G. Del Corso, Govanni Manzini "Matrix rank and communication complexity", посвященных связи между рангами некоторых матриц и сложности вычислений в линейной алгебре.

Семинар 5 декабря 2000 года

Вторник, 5 декабря, комната 106. Начало в 12:00.

Докладчик: В. Жижкун.

РАВЕНСТВА И ПЕРЕПИСЫВАНИЕ ТЕРМОВ
В докладе обсуждаются системы равенств и системы переписывания термов, некоторые их свойства (в частности, нетеровость, или остановочность) и связь этих свойств в проблемой разрешимости (теорема Кнута-Бендикса).

Семинар 28 ноября 2000 года

Вторник, 28 ноября, комната 106. Начало в 12:00.

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

АВТОМАТИЧЕСКОЕ ПОРОЖДЕНИЕ ДОКАЗАТЕЛЬСТВ В СЕКВЕНЦИАЛЬНЫХ ИСЧИСЛЕНИЯХ С РАВЕНСТВОМ
(продолжение)

Семинар 21 ноября 2000 года

Вторник, 21 ноября, комната 106. Начало в 12:00.

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

АВТОМАТИЧЕСКОЕ ПОРОЖДЕНИЕ ДОКАЗАТЕЛЬСТВ В СЕКВЕНЦИАЛЬНЫХ ИСЧИСЛЕНИЯХ С РАВЕНСТВОМ
впервые процедура поиска вывода в секвенциальном исчислении с равенством была предложена с. кангером в середине 50-х гг. однако, в отличие от метода резолюции, до сих пор не известен способ поиска доказательств в подобных исчислениях, который давал бы приемлемую производительность. будет сделан доклад на основе обзора А. Дегтярева и А. Воронкова "equality reasoning in sequent-based calculi", представляющий различные способы поиска секвенциальных доказательств с равенством.

Семинар 14 ноября 2000 года

Вторник, 14 ноября, комната 106. Начало в 12:00.

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

ОЦЕНКИ СНИЗУ НА МАКСИМАЛЬНОЕ КОЛИЧЕСТВО ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ ГРАФА
Будет доказано, что в любом связном графе, степени вершин которого не менее 3, можно выделить остовное дерево, в котором более 1/4 всех вершин висячие, а в любом связном графе, степени вершин которого не менее 4, можно выделить остовное дерево, в котором более 2/5 всех вершин висячие. будут приведены бесконечные серии примеров, показывающие оптимальность этих оценок.
Для связного графа, степени всех вершин которого не менее d (d>4) будет приведен алгоритм выделения остовного дерева с большим количеством висячих вершин, будут доказаны оценки снизу на количество висячих вершин в остовном дереве такого графа.

Syndicate content