What is the satisfiability threshold of random balanced Boolean expressions?

DOI10.1002/RSA.21069MaRDI QIDQ6076769zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Generalised and quotient models for random and/or~trees and application to satisfiability
• Balanced and/or trees and linear threshold functions
• Threshold properties of random Boolean constraint satisfaction problems
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• scientific article; zbMATH DE number 1256700

Cites work

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

Cited in

(1)

• Finite-depth scaling and an exact Bernoulli-leaf identity for the min-plus process on the binary tree

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076769)