Abstract: k-satisfiability is a constraint satisfaction problem where one wants to find the assignments of Boolean variables that satisfies a given set of constraints(or clauses). The problem is known to undergo phase transitions as a function of the ratio of constraints and variables. Phase transitions in random k-satisfiability problems are believed to be connected to their computational complexity. While polynomial time algorithms are known to solve the problem for k = 2, for k ≥ 3 the problem is known to be NP-complete. In this talk, we will discuss random k-satisfiability and many of its variants on regular trees. The solvability threshold for k = 2 matches the exact value of the threshold on regular random graphs. For higher k, the values are very close to those predicted using other techniques like the cavity method.
