Теоретический семинар

24 ноября, четверг, 17-00, к.203 (ПОМИ РАН)

Д. Тугарёв

О полных односторонних функциях

Будут представлены полные односторонних функции, основаннные на:

  • задаче поиска замощения;
  • полусистемах Туэ;
  • задаче Поста.

Будут формально представлены свойства, которыми должна обладать комбинаторная задача, чтобы на её основе можно было построить полную односторонюю функцию.

А.А.Кожевников, С.И. Николенко Проблемы передачи информации 2009 Вып.2 Т.45 О полных односторонних функциях.

1 декабря, четверг, 17-00, к.203 (ПОМИ РАН)

Байесовские сети

В докладе будет дано определение байесовской сети, введено понятие d-separation, показаны некоторые свойства графов и соответствующих им распределений.

R. Neapolitan. Learning Bayesian Networks

8 декабря, четверг, 17-00, к.203 (ПОМИ РАН)

Д. Сердюк

Графические модели: фактор-графы

На данной лекции будет введено понятие фактор-графа, маргинальных функций, соответствующих данной функции. Далее будет рассмотрен sum-product алгоритм для вычисления всех маргмнальных фунуций. В конце будет продемонстрировано, каким образом фактор-графы были применены для рейтинговой системы TrueSkill.

F.Kschischang Factor Graps and the Sum-Product Algorithm.
R.Herbrich, T.Minka, T.Graepel TrueSkill: A Bayesian Skill Rating System.

15, 22 декабря, четверг, 17-00, к.203 (ПОМИ РАН)

А. Витвицкий

Анализируется эффективность алгоритма случайного блуждания на случайных 3-КНФ формулах. Доказывается линейная верхняя граница на время работы этого алгоритма с плотностью дизъюнктов меньше 1.63. В доказательстве вводиться простое, но мощное средство анализа таких алгоритмов – понятие терминатора, взвешенного выполняющего набора. Показывается что любая КНФ формула имеющая терминатор небольшого веса, решается алгоритмом случайного блуждания за линейное время. Естественно встает вопрос о «терминальном пороге» - максимальной плотности дизъюнктов, для которой с большой вероятностью существует терминатор. Показывается что порог для эвристики свободного литерала (1.63) является нижней границей для терминального порога. Одно из свойств терминаторов то, что они могут быть эффективно найдены с помощью линейного программирования, что представляет эффективно вычислимый сертификат линейного времени работы простого алгоритма случайного блуждания.

Mikhail Alekhnovich, Eli Ben-Sasson. Linear Upper Bounds For Random Walk On Small Density Random 3-CNFs.

21 мая, пятница, 12.00, к.432

Ю. Беляева (АУ)
Семейства множеств с ограниченным размером пересечений и явная
конструкция графов Рамсея

В докладе будет рассказано о семействах множеств с ограниченным числом
пересечений. Семейство множеств называется L-пересекающимся, если
размер пересечения любых двух элементов из семейства принадлежит
множеству L. В докладе будут приведены оценки на размер
L-пересекающихся семейств для случаев равномерного и неравномерного
семейства. Также будет рассказано обобщение известного модульного
варианта этих оценок, доказанного в P.Frankl, R.M.Wilson "Intersection
theorems with geometric consequences", в котором рассматриваются не
сами размеры пересечений, а их остатки по некоторому простому модулю
p. Будут изложены доказательства, представленные в N.Alon, L.Babai,
H.Suzuki "Multilinear polynomials and Frankl - Ray-Chaudhuri - Wilson
type intersection theorems", использующие линейные пространства
полиномов. В качестве следствия рассказанных результатов будет
приведена явная конструкция графов Рамсея суперполиномиальным числом
вершин.

14 мая, пятница, 15.15, к.430

Ф. Парт (АУ)
Моделирование одной машины Тьюринга на другой

Доклад по материалам лекции А. Ромащенко. На докладе будет разобрана
проблема построения эффективной универсальной машины Тьюринга.
В частности, будет рассмотрен алгоритм моделирования многоленточной машины
Тьюринга на двухленточной с замедлением в логарифм.

16 апреля, пятница, 15.15, к.430

С. Капулкин (АФТУ)
p-оптимальные системы доказательств

По статье ''Optimal acceptors and optimal proof systems'', автор Э.А.Гирш.
Доклад является введением в проблематику систем доказательств и аксепторов. Поиск системы доказательств для языка тавтологий с доказательствами полиномиальной длины связан с вопросом $\mathbf{NP}$ vs $\mathbf{co{-}NP}$. Акспеторами называются машины, останавливающиеся на входах из языка и только на них. В докладе показывается связь между существованием p-оптимальных систем доказательств и оптимальных аксепторов. Доказывается существование p-оптимальных систем доказательств с одним битом подсказки.

2 апреля, пятница, 15.15, к.430

С. Исакова (АФТУ)
Схемная сложность обратных функций

Доклад по статье Jean-Camille Birget "On the circuit-size of inverses".
Фундаментальным в криптографии является вопрос о сложности обращения
функции. В рассматриваемой статье ключевым является несколько похожий
вопрос: "какого размера может быть обратная функция". Устанавливается связь
между такими, на первый взгляд, не очень связанными понятиями, как схемная
сложность обратных функций и классы сложности. А именно, в докладе будет
рассмотрена и доказана следующая теорема:
Если существует ограничение на размер обратной функции (точнее, если
существует полином, который для любой ациклической булевой схемы C
ограничивает размер обратной схемы C'), то полиномиальная иерархия
схлопывается до второго уровня.

24 февраля, среда, 14.00, к.430

С. Капулкин (АФТУ)
Иерархия по времени вычислений с подсказкой

Доклад по статье Melkebeek, Pervyshev "A Generic Time Hierarchy for Semantic Models With One Bit of Advice". В докладе будет рассмотрена иерархия по времени для семантических классов с подсказкой. Будет дано достаточно общее определение семантического класса, включающее в себя такие классы, как RP, BPP, AM и другие. Будет сформулирована и доказана следующая теорема:
Для любой разумной семантической модели вычислений и любых констант a и c найдется язык, вычислимый за полиномиальное время с одним битом подсказки, но не за время $n^c$ с $a$ битами подсказки.

23 апреля, пятница, 15.15, к.430

В. Николаенко (АФТУ)
Алгоритм Берлекэмпа

В этом докладе будет рассказано об алгоритме Берлекэмпа разложения полнимов на множители в полях простой мощности, и в качестве подзадаче о тесте на неприводимость. Будет также расказано, как улучшить оценку на время работы, сделав алгоритм вероятностным.