Talk information

Date: Sunday, January 08, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: József Balogh (University of Illinois at Urbana-Champaign)
Title: Nearly all $k$-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$ tends to infinity. This resolves a conjecture by Bollob'as, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras.

The lecture is summarizing results of a paper of Dingding Dong, Nitya Mani, and Yufei Zhao, and a follow-up paper with additional authors Bernard Lidický and the speaker.

The talk is aimed for a general audience, including computer scientists.