Seminars: A. S. Kulikov, Polynomial formulations as a barrier for reduction-based hardness proofs

SEMINARS


Joint Mathematical seminar of Saint Petersburg State University and Peking University October 31, 2024 15:00, St. Petersburg, online

Polynomial formulations as a barrier for reduction-based hardness proofs A. S. Kulikov Saint Petersburg State University
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^{\text{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. Language: English