SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$? Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations? 



Or if we specialize to Max-CUT do we know of graphs whose Max-CUT polynomial needs high SOS degree to be solved? (Or if we at least know of integrality gaps for it for high SOS degree)
We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.

You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c &lt; 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.

Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.