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

Докладчик: Иван Михайлин