Polynomial Interpolation for Sherali-Adams Lower BoundsResearch Paper
Sherali-Adams is the standard proof system for refuting unsatisfiable CNF formulas with linear programming. Its refutations are linear-programming certificates over products of literals, the same objects that underlie the Sherali-Adams hierarchy of LP relaxations (Sherali–Adams 1990). It polynomially simulates Resolution, the proof system whose lines are…