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