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.