Polynomial Interpolation for Sherali-Adams Lower Bounds
Nathan Acheampong, Ben Davis, Robert Robere
We prove Sherali-Adams is exponentially weaker than Res(2), and also that it is not automatable unless P = NP. This resolves an open question asked by many papers on the automatability of weak proof systems.
Submitted to STOC 2027.