Laboratory of Mathematical Logic at PDMI

Cреда, 12 июля, 203. Начало в 12:00.

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

Тема: Non-uniform lower bounds from uniform hardness assumptions.

Abstract

In the talk we are going to discuss new connections between time and
circuit complexities. While the approach is more or less generic, we
will focus on the complete examples. We will prove that plausible
assumption on time complexity of Max-3-SAT implies previously unknown
circuit lower bounds. While this is interesting on it's own it also
implies that proving that Max-3-SAT is SETH hard would give us some
non-uniform lower bound as a side product. One appealing feature of
this approach is that Max-3-SAT being SETH hard would be consistent
with current knowledge.