|
|
|
|
|
|
|
|
Év szerint | Hónap szerint | Ugrás a hónaphoz | |
|
Balogh József: Nearly all k-SAT functions are unate |
|
|
|
Péntek, 21. Július 2023, 10:00 - 11:00
|
|
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 Bollobas, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras. Joint work with: Dingding Dong (Harvard), Bernard Lidicky (Iowa State University), Nitya Mani (MIT), Yufei Zhao (MIT). |
Vissza
JEvents v3.1.8 Stable
Copyright © 2006-2013