# Среда 12.07. Иван Михайлин: "Non-uniform lower bounds from uniform hardness assumptions"

Speaker:

Иван Михайлин

Date:

Wednesday, July 12, 2017 - 12:00

Place:

203

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.