What is the satisfiability threshold of random balanced Boolean expressions?

Naomi Lindenstrauss Michel Talagrand

Published in: Random Struct. Algorithms (2022)

Keyphrases

boolean expressions
np complete
normal form
computational complexity
conjunctive queries
phase transition
satisfiability problem
multiresolution
database
information retrieval
decision trees
real valued