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

7.03.2013 16:00 ауд. 431 (Продолжение) Алгоритм выполнимости и средняя оценка времени работы для формул над полным двоичным базисом. (Сергей Савинов)

В докладе будет показан алгоритм для выполнимости булевых формул на основе полного двоичного базиса. Для формул размера не более cn, алгоритм работает за время 2^(1-с_0)n для некоторой константы c_0.

14.03.2013 16:00 ауд. 431 Gaussian Mixture Model and its Applications to Imaging Mass Spectrometry Data (Илья Чернявский)

В докладе будут рассмотрены графические модели и их частный случай -- Gaussian Mixture Model (GMM).
Будет рассмотрен алгоритм обучения, а также пример применения GMM к данным
изображающей масс-спектрометрии.

28.02.2013 16:00 ауд. 431 Алгоритм выполнимости и средняя оценка времени работы для формул над полным двоичным базисом. (Сергей Савинов)

В докладе будет показан алгоритм для выполнимости булевых формул на основе полного двоичного базиса. Для формул размера не более cn, алгоритм работает за время 2^(1-с_0)n для некоторой константы c_0.

21.02.2013 16:00 ауд. 431 Монотонные схемы размера O(n log n) для пороговых функций (Денис Тугарев)

В докладе будет рассмотрено построение монотонной формулы для k-ого элементарного симметрического многочлена от n булевых переменных. Эта формула будет иметь размер O(n logn) для фиксированного k и будет строиться за полиномиальное от n время.

05.12 и 12.12.2012 14-00 ПОМИ ауд. 106, Сложность в среднем для построения односторонних функций (Р.А. Демидов)

В докладе будет доказана теорема о невозможности построения парного самплера(а значит, и односторонней функции), выдающего пары (условие, решение з.п. R) по тотальной задаче поиска R', трудной на распределении, задаваемом полиномиальным сюрьективным самплером.

14.11 и 21.11.2012 14-00 ПОМИ ауд. 106 Нижняя оценка 3n - o(n) на сложность булевых схем (С.В. Савинов)

В докладе методом элиминации гейтов будет доказана нижняя оценка 3n - o(n) на сложность булевых схем, вычисляющих функцию Блюма.

31.10 и 7.11.2012 14-00 ПОМИ ауд. 106 Приближенные алгоритмы решения задачи о надстроке (Б.В. Парфененков)

В докладе будет рассмотрен приближенный алгоритм решения задачи о надстроке, использующий покрытие циклами в префекс-графе. Данный алгоритм позволяет получить приближение 2.5. В докладе будет изучен алгоритм для Max-ATSP Paluch, для которого доказан приближающий фактор 2/3.

17.10 и 24.10.2012 14-00 ПОМИ ауд. 106, Модель Latent Dirichlet Allocation и задача вывода (И,И. Чернявский)

В докладе будут рассмотрены байесовские сети и их частный случай -- модель LDA, также
будет рассмотрен алгоритм вывода на байесовской сети, основанный на сэмплировании.

10.10.2012 14-00 ПОМИ ауд. 106 Нижние и верхние оценки на схемную сложность некоторых функций (Д.С. Тугарев)

В докладе будут рассмотрены доказательства нижних и верхних оценок на схемную сложность функций, вычисляющих одновременно: AND и XOR; AND и OR.Также будет рассмотрена статья "A 5n-o(n) Lower Bound on the Circuit Size over U_2 of a Linear Boolean Function" Alexander S. Kulikov, Olga Melanich, and Ivan Mihajlin, и будет доказана соответствующая нижняя оценка для функции $f = Ax \oplus b$, где $A \in {0,1}^{m\times n}$ матрица с n-различными ненулевыми столбцами и $b \in {0,1}^m$ некоторый вектор.