Monotone real circuit

Speaker: 
Дмитрий Соколов (ПОМИ)
Date: 
Friday, September 30, 2016 - 14:00
Place: 
ПОМИ, ауд. 402
Abstract: 

В докладе рассмотрим доказательство нижних оценок на монотонные вещественные схемы для функции Broken Mosquito Screen. Доказательство основано на построениие заборов и идейно отличается от доказательства Разборова для Clique-Coloring.
Также мы докажем нижнюю оценку на Cutting Plane не ссылаясь на доказательство Пудлака.