# 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.