(#003) Randomized Algorithms, the Probabilistic Method and Derandomization through the lens of 3SAT - Arjun P
Date & Time: 05-09-2020, 21:00 IST
Abstract
We'll look at a trivial-looking randomized approximation algorithm for MAX-E3SAT, the problem of satisfying as many clauses as possible in a special kind of 3SAT instance. We'll then introduce the probabilistic method and see how it can use our algorithm to say something about the satisfiability of arbitrary E3SAT instances. Finally, we will discuss how one could obtain a deterministic approximation algorithm for the same problem.
Prerequisites
Basic probability and expectations, linearity of expectations, conditional expectation. Knowing what 3SAT and NP-Completeness are would be required to appreciate the significance, but not necessarily to follow the discussion [For the latter, consult any textbook on complexity theory, e.g., Arora-Barak]
Resources
This slideshow (page 7 & 8) are most of the content of the talk: https://cse.buffalo.edu/~hungngo/classes/2008/694/notes/rr-sat.pdf. From a quick google, I couldn't find anything that talks about it in more detail for this particular problem, but the ideas are the same. This technique for derandomization is called the method of conditional expectations.
For more on the probabilistic method, you can see the textbook titled (surprise!) the Probabilistic Method by Alon & Spencer.