Abstract
Given a constraint satisfaction problem (CSP) such as SAT, we look at the clause-variable incidence graph. What is the role of expansion of this graph when studying the computational hardness of this instance? Does expansion make instances easy or hard (or neither)?
In the talk we will see examples of both. Sometimes expansion is used for proving hardness (e.g. in the proof of the PCP theorem, and in concrete lower bounds such as for semidefinite hierarchies). In other parameter regimes expansion makes an instance amenable to spectral algorithms, and this leads, for example, to interesting algorithms for decoding error correcting codes.