Среда 12.07. Иван Михайлин: "Non-uniform lower bounds from uniform hardness assumptions"
PDMI seminars
Тема: Non-uniform lower bounds from uniform hardness assumptions
Место: 203
Время: 12.07.2017, 12:00
Докладчик: Иван Михайлин
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.