Starting in the mid-90's, it became gradually apparent that techniques from asymptotic convex geometry and the theory of finite-dimensional normed spaces were highly relevant to a variety of computational problems. At the center of this connection is the following task: Given a graph G = (V,E), find the subset of vertices which expands the least. In other words, the subset S of V with |S| <= 1/2 |V| for which the value of |E(S,V\S)|/|S| is minimal (as usual, E(S,V\S) denotes the set of edges crossing from S to its complement). Besides being quite natural, this problem - which goes by the names of GraphExpansion or SparsestCut - turns out to be extremely useful as a subroutine in divide-and-conquer approaches to a variety of NP-hard optimization problems.
Depending upon the exact phrasing, the expansion problem itself is either NP- or coNP-hard, so our attention turns to the goal of finding subsets whose expansion is only approximately minimal. When one begins to consider linear and semi-definite relaxations of the problem, beautiful connections with geometry and analysis emerge. Perhaps not surprisingly (in retrospect), the most basic of these involve the notion of isoperimetry in high-dimensional spaces.
For instance, it is a classical fact that amongst all subsets of the d-dimensional unit sphere, whose measure is half that of the whole sphere, the one with smallest "boundary" is a spherical cap. One consequence of this - part of the so-called concentration of measure phenomenon - is that every "well-behaved" real-valued function on the sphere is almost constant on almost the entire sphere (where the "almost" part becomes asymptotically negligible as d tends to infinity). On the one hand, we are used to problems becoming more and more difficult as the dimension increases, and on the other hand we see that high-dimensional spaces can exhibit a surprising amount of regularity and simplicity which we can seek to exploit algorithmically.
Recent work suggests that this connection is fundamental - not only can we use geometric and analytic tools to help solve such problems, but these notions are intrinsically linked to the hardness/tractibility of problems that were, a priori, purely combinatorial. This link arises through the construction and analysis of new PCPs (probabilistically checkable proofs), which rely on a more elusive type of isoperimetric phenomenon involving the notion of stability. In this genre, we are concerned not only with the optimal cuts (minimally expanding sets), but also the structure of near-optimal cuts, and whether such cuts must themselves be "close" to an optimal cut. In this pursuit, harmonic analysis of boolean-valued functions is an essential tool.
I will discuss the key ideas surrounding recent progress in this field, and attempt to give an intuitive overview of the tools and techniques involved.