Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-288 | 30th October 2026 21:38

Polynomial Interpolation for Sherali-Adams Lower Bounds

RSS-Feed




TR26-288
Authors: Nathan Acheampong, Ben Davis, Robert Robere
Publication: 30th October 2026 22:16
Downloads: 30
Keywords: 


Abstract:

We resolve two open problems regarding the Sherali-Adams proof system. First, we show that Res(2), which manipulates 2-DNF formulas, is exponentially stronger than Sherali-Adams. This provides a sharp separation in power between Sherali-Adams and the bounded-depth Frege hierarchy, as Sherali-Adams polynomially simulates Resolution. Second, we prove that Sherali-Adams is not size-automatable unless P = NP. This resolves an open problem on the automatability of weak proof systems asked by many researchers. Both of these results are obtained by using a new technique for proving lower bounds on Sherali-Adams degree via polynomial interpolation.



ISSN 1433-8092 | Imprint