Polynomial formulations as a barrier for reduction-based hardness proofs

• 主讲人：Alexander Kulikov (Saint Petersburg State University)
• 举办方： Beijing-Saint Petersburg Mathematics Colloquium
• 时间： 2024-10-31 20:00 - 2024-10-31 21:00
• 地点： Online

​

Recording: https://disk.pku.edu.cn/link/AABCAC4B4FB4294DCEAE32637CBB69A429

 

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.

 

Bio: Professor Alexander S. Kulikov has graduated from Saint Petersburg State University at 2005, has got his PhD degree in 2009 and Doctor of Science degree at 2017 (under supervision of Prof. A Hircsh, the topic of his thesis was Complexity of Explicitly Defined Boolean Functions).

Prof. Kulikov combines a full-professor position at the Faculty of Mathematics and Computer Science at Saint Petersburg State University with that of Senior Research Fellow of Steklov Institute. Besides, he is the founder and a board member of the Computer Science Center at Steklov Institute.

Prof. Kulikov is a top-level expert in Logics, Algorithms, and Complexity Theory. He has got 44 research papers and one book in these areas. Moreover, he has got some prestigious prized, including Best Young Researcher Award by Steklov Institute of Mathematics at St. Petersburg, Russian Academy of Science and Scopus Award Russia by Elsevier.