What is the satisfiability threshold of random balanced Boolean expressions?

DOI10.1002/RSA.21069OpenAlexW4200376990MaRDI QIDQ6076769

Naomi Lindenstrauss, Michel Talagrand

Publication date: 17 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.21069

Mathematics Subject Classification ID

Combinatorial probability (60C05) Computational aspects of satisfiability (68R07)

Cites Work

• Generalised and quotient models for random and/or~trees and application to satisfiability
• The asymptotic \(k\)-SAT threshold
• A sprouting tree model for random boolean functions
• Some typical properties of large AND/OR Boolean formulas
• And/or trees: A local limit point of view
• Balanced And/Or trees and linear threshold functions

This page was built for publication: What is the satisfiability threshold of random balanced Boolean expressions?