Yufei Zhao (MIT) - Enumerating k-SAT functions
How many k-SAT functions on n boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that for each fixed k, almost every k-SAT function is unate. In this talk, I will discuss progress towards this conjecture and explain how the hypergraph container method can be used to reduce the problem to a hypergraph Turán-like problem, which is solved for k ≤ 4 but remains open in general.
Joint work with Dingding Dong and Nitya Mani
Host: Alexander Razborov
Speakers
Yufei Zhao
Yufei Zhao is Assistant Professor of Mathematics at the Massachusetts Institute of Technology. He received his PhD from MIT in 2015 and has previously held positions at Oxford, Berkeley, Stanford, and Microsoft Research. He has been awarded the SIAM Dénes Kőnig prize (2018), the Sloan Research Fellowship (2019), and the NSF CAREER Award (2021). His research tackles a broad range of problems in discrete mathematics, including extremal, probabilistic, and additive combinatorics, graph theory, and discrete geometry, as well as applications to computer science.
