Nearly All-SAT Functions Are Unate

József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. 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án problem on partially directed hypergraphs. In this paper we solve this Turán problem.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages958-962
Number of pages5
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

Keywords

  • Turan problems
  • hypergraph container method
  • k-SAT function
  • sum of squares

ASJC Scopus subject areas

  • Software

Cite this