@inproceedings{70ac6a685dbd4865b195328d54ca4962,

title = "Nearly All-SAT Functions Are Unate",

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{\'a}s, Brightwell, and Leader from 2003. This paper is the second half of a two-part work solving the problem. The first part, by Dong, Mani, and Zhao, reduces the conjecture to a Tur{\'a}n problem on partially directed hypergraphs. In this paper we solve this Tur{\'a}n problem.",

keywords = "Turan problems, hypergraph container method, k-SAT function, sum of squares",

author = "J{\'o}zsef Balogh and Dingding Dong and Bernard Lidick{\'y} and Nitya Mani and Yufei Zhao",

note = "Publisher Copyright: {\textcopyright} 2023 Owner/Author.; 55th Annual ACM Symposium on Theory of Computing, STOC 2023 ; Conference date: 20-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "2",

doi = "10.1145/3564246.3585123",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "958--962",

editor = "Barna Saha and Servedio, {Rocco A.}",

booktitle = "STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing",

address = "United States",

}