Home

Вторник 17.09. А.С. Куликов: "Polynomial formulations as a barrier for reduction-based hardness proofs"

Вторник, 17 сентября, Zoom . Начало в 14:00.

Докладчик: А.С. Куликов (ПОМИ).

Тема: Polynomial formulations as a barrier for reduction-based hardness proofs.

Abstract

The Strong Exponential Time Hypothesis (SETH) postulates that SAT cannot be solved in less than $ 2^n $ steps. In recent years, many SETH-based lower bounds have been proven: for example, $ n^2 $ for Edit Distance, $ 2^n $ for Hitting Set, $ 2^{treewidth} $ for Independent Set. One may speculate that SETH can explain many other current algorithmic barriers. In the talk, we'll show that, for many problems, an SETH lower bound would imply new circuit lower bounds.