@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 = "The collaboration that led to this paper started when Zhao presented [7] at an Oberwolfach workshop in 2022, with Balogh also in attendance. This work used the computing resources at the Center for Computational Mathematics, University of Colorado Denver, including the Alderaan cluster, supported by the National Science Foundation award OAC-2019089. Balogh was supported in part by NSF grants DMS-1764123 and RTG DMS-1937241, FRG DMS-2152488, the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC). Lidick{\'y} was supported in part by NSF grant FRG DMS-2152490 and Scott Hanna fellowship. Mani was supported by the NSF Graduate Research Fellowship Program and a Hertz Graduate Fellowship. Zhao was supported in part by NSF CAREER award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum Fund.; 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",
}