STOC2023
Nearly All k-SAT Functions Are Unate
József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao
4 citations
Abstract
We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.