Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections

Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler

We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees sat…