Let rho = E[Pi_{(i,j) \in S} f(x^{(i)}x^{(j)}) f(x^{(i)})f(x^{(j)})]. Without loss of generality, assume (1,2) is an edge in S. Show that there are settings for x^{(3)}...x^{(k)} so that E_{x^{(1)},x^{(2)}}[Pi_{(i,j) \in S} f(x^{(i)}x^{(j)}) f(x^{(i)})f(x^{(j)})] is at least rho. Now show that an argument similar to that of problem 1 (linear consistency testing) gives the bound.