We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least 2-\epsilon after
\Omega_\epsilon(\log n) rounds, where n is the number of
vertices, and Tourlakis proves that integrality gap remains at least
1.5-\epsilon after \Omega((\log n)^2) rounds. Fernandez de la
Vega and Kenyon prove that the integrality gap of Max Cut is at most
1/2 + \epsilon after any constant number of rounds. (Their
result also applies to the more powerful Sherali-Adams method.)

We prove that the integrality gap of Vertex Cover remains at least
2-\epsilon after \Omega_\epsilon (n) rounds, and that the
integrality gap of Max Cut remains at most 1/2 +\epsilon after
\Omega_\epsilon(n) rounds.

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least 2-\epsilon after
\Omega_\epsilon(\log n) rounds, where n is the number of
vertices, and Tourlakis proves that integrality gap remains at least
1.5-\epsilon after \Omega((\log n)^2) rounds. We are not aware
of previous work on Lovasz-Schrijver linear programming relaxations
for Max Cut.

We prove that the integrality gap of Vertex Cover remains at least
2-\epsilon after \Omega_\epsilon (n) rounds, and that the
integrality gap of Max Cut remains at most 1/2 +\epsilon after
\Omega_\epsilon(n) rounds. The result for Max Cut shows a gap
between the approximation provided by linear versus semidefinite
programmming relaxations.