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.

[ECCC]

Talk at Newton Institute (October 2026), [Part 1], [Part 2]