Lift-and-project procedures are systematic techniques for 
strengthening mathematical programming relaxations of 
optimization problems. Determining whether the solutions
to such lift-and-project relaxations can be used to obtain
improved approximation algorithms is an interesting 
question. We show integrality gaps for Sherali-Adams
lift-and-project relaxations for several optimization 
problems such as Max Cut, Vertex Cover, 
Maximum Acyclic Subgraph, Sparsest Cut and other problems.

The main combinatorial challenge in constructing these gap 
examples is the construction of a fractional solution that 
is far from an integer solution, but yet admits consistent 
distributions of local solutions for all small subsets of 
variables. Satisfying this consistency requirement is one of 
the major hurdles to constructing Sherali-Adams gap examples. 

We present a modular recipe for achieving this, based on 
metrics with a local-global structure. Roughly speaking,
such metrics have good local properties (every small subset
embeds isometrically into l_1), yet exhibit poor global 
structure (i.e. a very high distortion is needed for embedding 
the entire metric into l_1). The talk will outline the 
construction of these local-global metrics and explain how they 
lead to integrality gaps for Sherali-Adams relaxations.