Enumerating k-SAT functions

Yufei Zhao Massachusetts Institute of Technology


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.

Mar 29, 2022 3:30 PM — 5:00 PM
Theory Seminar