## Randomized k-SAT algorithm

Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals.

• Give a Las Vegas algorithm that finds an assignment satisfying at least $m(1-2^{-k})$ clauses, and analyze its expected running time.
• Give a derandomization of the randomized algorithm using the method of conditional expectation.
Source: from book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis"
delete retag edit Add to a Problem Set