UC Berkeley

Hard combinatorial optimization problems are often approximated using linear or semidefinite programming relaxations. In fact, most of the algorithms developed using such convex programs have special structure: the constraints imposed by these algorithms are local i.e. each constraint involves only few variables in the problem. In this thesis, we study the power of such local constraints in providing an approximation for various optimization problems.

We study various models of computation defined in terms of such programs with local constraints. The resource in question for these models is are the sizes of the constraints involved in the

program. Known algorithmic results relate this notion of resources to the time taken for computation in a natural way.

Such models are provided by the ``hierarchies" of linear and semidefinite programs, like the ones defined by Lov {a}sz and Schrijver; Sherali and Adams; and Lasserre. We study the complexity of approximating various optimization problems using each of these hierarchies.

This thesis contains various lower bounds in this computational model. We develop techniques for reasoning about each of these hierarchies and exhibiting various combinatorial objects whose local properties are very different from their global properties. Such lower bounds {\em unconditionally} rule out a large class of algorithms (which captures most known ones) for approximating the problems such as MAX 3-SAT, Minimum Vertex Cover, Chromatic Number and others studied in this thesis.

We also provide a positive result where a simple semidefinite relaxation is useful for approximating a constraint satisfaction problem defined on graphs, if the underlying graph is expanding. We show how expansion connects the local properties of the graph to the global properties of interest, thus providing a good algorithm.