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

06.03.2014 (Сергей Савинов) Субэкспоненциальные алгоритмы, нижние оценки.

Обсудим субэкспоненциальные алгоритмы: введём $SERF$-сведение и докажем полноту относительно него для некоторых задач. Также рассмотрим вопрос о доказательстве нижних оценок. Рассмотрим нижние оценки для $AC^0$. Покажем, что с большой долей вероятности случайные полиномы второй степени для $GF(2)$ требуют экспоненциальный размер для схем $\Sigma_3^k$ при $k=o(\log \log n)$. Как следствие, получим пcевдослучайный генератор.

20.02.2014 (Ваня Михайлин) Saving Space by Algebraization.

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

7.11.2013, 14.11.2013 (Кирилл Елагин) Введение в теорию типов и termination checking

В докладе рассмотрены базовые понятия и ключевые результаты теории лямбда-исчисления: термы, нормализации, бета-редукция. теорема Черча-Россера. Особое внимание уделено связи лямбда-исчисления с теорией рекурсии. Так же будут рассмотрены простейшие способы типизации лямбда-исчисления: просто типизированное лямбда-исчисление, System T Гёделя. Представлен алгоритм foetus, позволяющий проверять, что программа завершает исполнение за конечное время на всех входах.

31.10.2013 (Павел Чуприков) Нижняя и верхняя оценки на время работы FIFO-алгоритмов обработки сетевых пакетов.

Будет представлена математическая модель процесса обработки разнотипных пакетов в сетевых процессорах. Приведена классификация FIFO-алгоритмов обработки и методика их сравнения. Рассмотрен частный случай таких алгоритмов - ленивые алгоритмы, предоставляющие удобную инфраструктуру для дальнейшего исследования. Доказаны верхние и нижние оценки на время работы ленивых FIFO-алгоритмов.

28.11.2013 (Сергей Савинов) Новый алгоритм выполнимости схемы.

В данной работе получена более сильная верхняя оценка $O(2^{.389667m})$ (по сравнению с $O(2^{.4058m})$, полученной ранее) в худшем случае для задачи выполнимости схемы над полным бинарным базисом, где m - число гейтов схемы.

19.12.2013 (Миша Слабодкин) The Depth of Resolution Proofs Alasdair Urquhart.

This paper investigates the depth of resolution proofs, that is to say,
the length of the longest path in the proof from an input clause to the
conclusion. An abstract characterization of the measure is given, as well
as a discussion of its relation to other measures of space complexity for
resolution proofs.

21.11.2013 (Ваня Михайлин) Вариации Direct Sum Theorem для запросовой и коммуникационной сложности.

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

12.12.2013 (Роман Демидов) Эффективные алгоритмы бикластеризации.

В своем докладе я расскажу о задаче бикластеризации(biclustering/coclustering), её применении к анализу многомерных данных масс-спектрометриии мозга и расскажу о различных алгоритмах/подходах к её решению.

17.10.2013 (Роман Демидов) Matrix Factorization through Latent Dirichlet Allocation

На семинаре я расскажу об fLDA(f - Latent Dirichlet Allocation) - новом методе предсказания рейтингов в рекомендательных системах, когда условные "документы", естественно представляются как "мешки слов"(bag-of-words).