Since polynomial-time algorithms are not expected to solve NP-hard problems, a well-established line
of work has sought lower bounds on the efficacy of these
algorithms; see [1]}, [2]}, [3]}, [4]}, [5]}
for lower bounds on LPs arising from lift-and-project hierarchies such as that of Sherali-Adams, [6]}, [7]}, [8]} for lower bounds on SDPs, and [9]} for lower bounds on linear Diophantine equations.
If, as conjectured by Garey and Johnson [10]}, AGC is NP-hard and P\(\ne \) NP, neither of the two algorithmic techniques should be able to solve it. This is indeed the case!
In a striking sequence of
works
by Dinur, Khot, Kindler, Minzer, and Safra [11]}, [12]}, [13]}, [14]},
the 2-to-2 conjecture of Khot [15]} (with imperfect completeness)
was resolved. As detailed in [14]}, this implies
(together with [17]}) that the sum-of-squares hierarchy does not solve AGC, which implies the same result for the weaker Sherali-Adams and bounded width hierarchies.
Regarding the second type of algorithms, very recent work
of Ciardo and Živný established that the \(\operatorname{AIP}\)  hierarchy does not solve AGC [18]}.
