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

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

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

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

В докладе будут рассмотрены доказательства нижних и верхних оценок на схемную сложность функций, вычисляющих одновременно: 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$ некоторый вектор.

В докладе будут рассмотрены классы сложности для задач комбинаторной оптимизации, такие как PO, NPO, APX, PTAS, FPTAS и будут показаны строгие включения NPO $\supset$ APX $\supset$ PTAS $\supset$ FPTAS.

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

В докладе будет рассказано, как эффективно решать задачу о наименьшей общей надстроке для ее частных, но все еще NP-полных случаев. Будут представлены 2 алгоритма:
1)находящий точное решение для случая, когда все строки длины не больше 3, за $3^{n/3}$, вместо лучшего известного, дающего $2^n$ для общего случая.
2)дающий лучшее приближение чем имеющиеся на данный момент приближающие алгоритмы для общего случая если все строки короче 7 символов.

В докладе мы познакомимся с понятиями систем доказательств и аксепторов для языков. Будет доказана теорема Месснера о том, что существование оптимальных аксепторов эквивалентно существованию p-оптимальных систем доказательств. Вторая часть доклада будет посвящена существованию оптимальных эвристических аксепторов и систем доказательств.