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.

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

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

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

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

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

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

Получение нижних оценок на размер резолюционных доказательств для задачи поиска противоречия в паросочетании на двудольном графе с разным числом вершин.

Пусть даны n точек на плоскости и еще три выделенных.
Псевдотреугольник неформально определяется, как треугольник, у которого вместо сторон выпуклые внутрь ломаные. При этом стороны не должны пересекаться.
Вершинами треугольника являются три выделенных точки, вершинами ломаных являются какие-то из n данных точек.

Будут рассказаны алгоритмы для решения следующих задач про псевдотреугольники:

1. Сколько пустых псевдотреугольников можно построить на n точках?
2. Сколько пустых звездных псевдотреугольников можно построить на n точках?
3. Построить псевдотреугольник (звездный псевдотреугольник), если такой существует.

Все алгоритмы будут использовать O(n^2) элементарных операций с точками и O(n) слов дополнительной памяти.

В докладе будет рассмотрен класс задач разбиения множества на подмножества удовлетворяющие какому-то полиномиально проверяемому свойству. Известен алгоритм, который решает задачу такого вида за 2^n. Так же, известно, что если ограничиться, вместо множеств, графами ограниченной степени, то решение может быть найдено за (2-eps)^n (где eps зависит только от максимальной степени графа). Не так давно был поставлен вопрос, можно ли получить аналогичные оценки для графов ограниченной средней степени.
В докладе будет дан утвердительный ответ для некоторых частных случаев. Будет рассказан метод, позволяющий получить ускорение, в случаи если задача допускает локальные ограничения определенного вида. Будет показано, как с помощью этого метода получить оценки вида (2-eps)^n для задачи коммивояжера и нахождения хроматического числа графа и задачи о поиске кратчайшей надстроки.