Monotone real circuit
Speaker:
Дмитрий Соколов (ПОМИ)
Date:
Friday, September 30, 2016 - 14:00
Place:
ПОМИ, ауд. 402
Abstract:
В докладе рассмотрим доказательство нижних оценок на монотонные вещественные схемы для функции Broken Mosquito Screen. Доказательство основано на построениие заборов и идейно отличается от доказательства Разборова для Clique-Coloring.
Также мы докажем нижнюю оценку на Cutting Plane не ссылаясь на доказательство Пудлака.