From Hall’s Marriage Theorem to Boolean Satisfiability and Back

Jonathan Lenchner, IBM T.J. Watson Research Center

Date and time: 6pm, Tuesday, April 9, 2019

Place: Courant Institute, WWH1314

I will describe an interesting connection between a famous combinatorial result known as Hall’s Marriage Theorem and Boolean Satisfiability (SAT) via a generalization of the Marriage Problem (the problem that the famous theorem is about) that I call the Fractional Marriage Problem, or FMP. I will describe how Hall's Marriage Theorem and the FMP come up in the context of an important technique in the approximability of facility location problems known as LP rounding. I will show that the Marriage Problem encodes a new family of polynomially satisfiable SAT formulas, different from the classically known polynomially solvable SAT variants, 2-SAT, Horn-SAT and XOR-SAT. I will then describe a program for dicing up the SAT landscape (or the landscape of any other NP-Complete problem) via translations from problems in P. Time permitting I will open up the floor for a brief discussion of this program, and otherwise we can have this discussion over dinner.