Lecture 7: The evasiveness conjecture

Continuing our look at some toplogical methods, today we’ll see the evasiveness conjecture in decision tree complexity.  In the next lecture, we’ll see how we can sometimes analyze the complexity using fixed point theorems, and their generalizations (like the Hopf index formula), following the work of Kahn, Saks, and Sturtevant.  These two lectures are co-blogged with Elisa Celis, with a lot of input from Lovasz’s lecture notes.

Decision tree complexity and evasiveness

Consider a boolean function on n bits.  We define the decision tree complexity of f as follows.  Given an unknown input , you are allowed to ask about the values of various bits of x, e.g. .  Your goal is to compute using as few questions as possible, and your questions can be adaptive, depending on answers to previous questions.  The complexity of such a strategy is the maximum number of questions asked for any .  The decision tree complexity, written , is the minimum complexity of any strategy that computes f.  (There are many other interesting models of decision complexity, see e.g. this survey.)

Clearly , because we can trivially query all the bits of x, and then output f(x).  A function f is called evasive if this upper bound is met, i.e. .  As an example, consider the parity function , where is addition modulo 2.  Clearly is evasive because after bits of x are asked about, the setting of the final bit determines the value of f.

For a more general example, consider any such that is odd.  In this case, for every , exactly one of or has the same property that the number of inputs resulting in a 1 is odd.  (These two functions are the natural restriction of f to functions on n-1 bits, which results from fixing the value of the ith bit.)  Thus an adversary could keep answering questions “?” so that the restricted function retains this property.  Since the number of inputs yielding a 1 is always odd, the restricted function always takes both possible values, implying that f is evasive–the advesary ensures that the value cannot be determined until all n possible questions are asked.

For an example of a non-evasive property, think of a point as speciying a directed graph on vertices, where there is exactly one directed edges connecting every pair of vertices, and x specifies the direction of this edge (this is called a tournament).  Thinking of the vertices as players, a directed edge from u to v means that u defeats v.  Now if the digraph specified by x has one vertex that defeats everyone else.  What is ?

Well, first we can conduct a single elimination tournament, where vertex 1 plays vertex 2, and the winner players vertex 3, and the winner of that players vertex 4, etc.  At the end, there is only one remaining vertex that remains undefeated.  Now asking more questions, we can determine whether indeeds defeats everyone else.  The total number of questions was , hence , implying that f is not evasive.

Montone graph properties and the evasiveness conjecture

Let .  In general, we can encode an arbitrary undirected N-vertex graph as an element .  A function is called a graph property if relabeling the vertices of doesn’t affect the value of .  The function f is monotone if the value of the function can never change from 1 to 0 when flipping one of the input bits from 0 to 1.  In the setting of graph properties, this corresponds to those which are maintained under addition of edges to the graph, e.g. “is G connected?” or “does G have a k-clique?”

Evasiveness Conjecture (Aanderaa-Karp-Rosenberg): Every non-trivial monotone graph property is evasive.

Here, non-trivial means that , where and denote the all-zeros and all-ones strings, respectively.

For example, consider the example “is G connected?”  The adversary is simple:  When asked about a possible edge , she answers NO unless this answer would imply that the graph is disconnected.  In other words, she answers NO unless she has answered NO already for all edges across a cut except for , in which case she has to answer YES.

Now, suppose there is a strategy which figures out the connectivity of without asking a question about some edge .  In this case, the conclusion must be that because the adversary always maintains that by answering everything in the future YES, she could force the graph to be connected.  In this case, the edges answered YES have to form a spanning tree of G (otherwise by answering all unasked questions NO, the graph would become disconnected).  Consider a path P from i to j in this YES spanning tree.  Let be the edge of P which was asked about last.  Clearly the adversary answered YES for , but this contradicts the advesary’s strategy.  Since has not been asked yet, the adversary is safe to answer NO for , and still later by answering YES on , she could force the graph to be connected.  Thus no such strategy exists, and connectivity is evasive.

Lecture 6: Borsuk-Ulam and some combinatorial applications

Now we’ll move away from spectral methods, and into a few lectures on topological methods.  Today we’ll look at the Borsuk-Ulam theorem, and see a stunning application to combinatorics, given by Lovász in the late 70′s.  A great reference for this material is Matousek’s book, from which I borrow heavily.  I’ll also discuss why the Lovász-Kneser theorem arises in theoretical CS.

The Borsuk-Ulam Theorem

We begin with a statement of the theorem.  We will think of the n-dimensional sphere as the subset of given by

Borsuk-Ulam Theorem: For every continuous mapping , there exists a point with .

Pairs of points are called antipodal.

There are a couple of common illustrative examples for the case .  The theorem says that if you take the air out of a basketball, crumple it (no tearing), and flatten it out, then there are two points directly on top of each other which were antipodal before.  Another common example states that at every point in time, there must be two points on the earth which both have exactly the same temperature and barometric pressure (assuming, of course, that these two parameters vary continuously over the surface of the eath).

The n=1 case is completely elementary.  For the rest of the lecture, let’s use and to denote the north and south poles (the dimension will be obvious from context).  To prove the n=1 case, simply trace out the path in starting at and going clockwise around .  Simultaneously, trace out the path starting at and going counter-clockwise at the same speed.  It is easy to see that eventually these two paths have to collide:  At the point of collision, .

We will give the sketch of a proof for   Let , and note that our goal is to prove that for some .  Note that is antipodal in the sense that for all .  Now, if for every , then by compactness there exists an such that for all .  Because of this, we may approximate arbitrarily well by a smooth map, and prove that the approximation has a 0.  So we will assume that itself is smooth.

Now, define by , i.e. the north/south projection map.  Let be a hollow cylinder, and let be given by so that linearly interpolates between and .

Also, let’s define an antipodality on by .  Note that is antipodal with respect to , i.e. , because both and are antipodal.  For the sake of contradiction, assume that for all .

Now let’s consider the structure of the zero set .  Certainly since , and these are h’s only zeros.  Here comes the sketchy part:  Since is smooth, is also smooth, and thus locally can be approximated by an affine mapping .  It follows that if is not empty, then it should be a subspace of dimension at least one.  By an arbitrarily small perturbation of the initial , ensuring that is sufficiently generic, we can ensure that is either empty or a subspace of dimension one.  Thus locally, should look like a two-sided curve, except at the boundaries and , where (if non-empty) would look like a one-sided curve.  But, for instance, cannot contain any Y-shaped branches.

It follows that is a union of closed cycles and paths whose endpoints must lie at the boundaries and .  ( is represented by red lines in the cylinder above.)  But since there are only two zeros on the sphere, and none on the sphere, must contain a path from to   Since is antipodal with respect to , must also satisfy this symmetry, making it impossible for the segment initiating at N to ever meet up with the segment initiating at S.  Thus we arrive at a contradiction, implying that must take the value 0.

Notice that the only important property we used about (other than its smoothness) is that is has a number of zeros which is twice an odd number.  If had, e.g. four zeros, then we could have two -symmetric paths emanating from and returning to the bottom.  But if has six zeros, then we would again reach a contradiction.

Lecture 5: Uniformizing graphs, multi-flows, and eigenvalues

In the previous lecture, we gave an upper bound on the second eigenvalue of the Laplacian of (bounded degree) planar graphs in order to analyze a simple spectral partitioning algorithm.  A natural question is whether these bounds extend to more general families of graphs.  Well-known generalizations of planar graphs are those which can be embedded on a surface of fixed genus, and, more generally, families of graphs that arise by forbidding minors.  In fact, Spielman and Teng conjectured that for any graph excluding as a minor, one should have .   Of course planar graphs have genus 0, and by Wagner’s theorem, are precisely the graphs which exclude and as minors.  In this lecture, we will follow an intrinsic approach of Biswal, myself, and Rao which, in particular, is able to resolve the conjecture of Spielman and Teng.  First, we see why even pushing the conformal approach to bounded genus graphs is difficult.

Bounded genus graphs

For graphs of bounded genus, there is hope to use an approach based on conformal mappings.  In 1980, Yang and Yau proved that

for any compact Riemannian surface of genus .  (Note that for the Laplace-Beltrami operator, one usually writes as the first non-zero eigenvalue, rather than .)  In analog with Hersch’s proof of the genus 0 case, they use Riemann-Roch to obtain a degree- conformal mapping to the Riemann sphere, then try to pull back a second eigenfunction.  A factor of the degree is lost in the Rayleigh quotient (hence the factor in the preceding bound), and Hersch’s Möbius trick is still required.

genus 0

genus 1

genus 2

genus 3

An analogous proof for graphs of bounded genus would proceed by constructing a circle packing of on the sphere , but instead of the circles having disjoint interiors, we would be assured that every point of is contained in at most circles.  Unfortunately, such a result is impossible (this has to do with the handling of branch points in the discrete setting).  Kelner has to take a different approach in his proof that for graphs of genus at most .

He starts with a circle packing of on a compact surface of genus (whose existence follows from results of Beardon and Stephenon and He and Schramm).  Then Kelner randomly subdivides repeatedly, and these subdivisions give progressively better approximations to some sequence of surfaces .  Once the approximation is of high enough quality, one applies Riemann-Roch to , and infers something about a subdivision of .  The final element is to track how the second eigenvalue of changes (in expectation) under random subdivision.

Needless to say, this approach is already quite delicate, and for graphs that can’t be equipped with some kind of conformal structure, we seem to have reached a dead end.  In this lecture, we’ll see how to use intrinsic deformations of the geometry of in order to bound its eigenvalues.  Eventually, this will reduce to the study of certain kinds of multi-commodity flows.

Metrics on graphs

Let be an arbitrary n-vertex graph with maximum degree .  Recall that we can write

where .  (Also recall that we can replace by any Hilbert space, and the same formula holds.)  The first step is to prepare this equality for “non-linearization” by getting rid of the linear condition and the sum .  (This is a popular sort of passage in the non-linear geometry of Banach spaces, which also plays a rather important role in applications to the theoretical CS.)  The goal is to get only terms that look like .  Fortunately, there is a well-known way to do this:

which follows easily from the equality when .

Thus if we want to bound , we need to find an for which the latter ratio (without the ) is .  Now, for someone who works a lot with linear programming relaxations, it’s very natural to consider a “relaxation”

where the minimization is over all pseudo-metrics d, i.e. symmetric non-negative functions which satisfy the triangle inequality, but might have even for .  Certainly , but Bourgain’s embedding theorem (which states that every n-point metric space embeds into a Hilbert space with distortion at most ) also assures us that .  Since we are trying to show that , this term is morally negligible.  One can see the paper for a more advanced embedding argument that doesn’t lose this factor, but for now we concentrate on proving that .  The embedding theorems allow us to concentrate on finding an intrinsic metric on the graph with small “Rayleigh quotient,” without having to worry about an eventual geometric representation.

As a brief preview… we are going to find a good metric by taking a certain kind of all-pairs multi-commodity flow at optimality, and weighting the edges by their congestion in the optimal flow.  Thus as the flow spreads out on the graph, it has the effect of “uniformizing” its geometry.

Discrete Riemannian metrics, convexification, and duality

Let’s now assume that is planar.  We want to show that .  First, let’s restrict ourselves to vertex weighted metrics on .  Given any non-negative weight function , we can define the length of a path in by summing the weights of vertices along it:  .  Then we can define a vertex-weighted shortest-path pseudo-metric on in the natural way

where is the set of all u-v paths in .  We also have the nice relationship

since .

So if we define

then by (1), we have .

Examples. Let’s try to exhibit weights for two well-known examples:  the grid, and the complete binary tree.

For the grid, we can simply take for all .  Clearly .  On the other hand, a random pair of points in the grid is apart, hence .  It follows that , as desired.

For the complete binary tree with root , we can simply put and for .  (Astute readers will guess the geometrically decreasing weights are actually the optimal choice.)  In this case, , while all the pairs on opposite sides of the root have .  It again follows that .  Our goal is to provide such a weight for any planar graph.

Lecture 4: Conformal mappings, circle packings, and spectral geometry

In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetition theorem for unique games.  In practice, spectral methods are a very successful heuristic for graph partitioning, and in the present lecture we’ll see how to analyze these partitioning algorithms for some common families of graphs.

Balanced separators, eigenvalues, and Cheeger’s inequality

Lipton and Tarjan proved that every planar graph has a negligibly small set of nodes whose remval splits the graph into two roughly equal pieces.  More specifically, every n-node planar graph can be partitioned into three disjoint sets such that there are no edges from to , the separator has at most nodes, and .  This allows one to do all sorts of things, e.g. a simple divide-and-conquer algorithm gives a linear time -approximation for the maximum independent set problem in such graphs, for any .

So there is a natural question of how well spectral methods do, for example, on planar graphs.  Spielman and Teng showed that for bounded-degree planar graphs, a simple recursive spectral algorithm recovers a partition of the vertex set so that .  In other words, for bounded-degree planar graphs, spectral methods recover the Lipton-Tarjan separator theorem!  This is proved by combining Cheeger’s inequality with their main theorem.

Theorem [Spielman-Teng]: Every n-node planar graph with maximum degree has , where is the second eigenvalue of the combinatorial Laplacian on .

Recall that we introduced the combinatorial Laplacian in Lecture 2.  If is an arbitrary finite graph, in this lecture it will make more sense to think about the Laplacian as an operator on functions given by

If we define the standard inner product , then one can easily check that for any such , we have .  In particular, this implies that is a positive semi-definite operator.  If we denote its eigenvalues by , then it is also easy to check that , with corresponding eigenfunction for every .

Thus by standard variational principles, we have

Let us also define the Cheeger constant .  For an arbitrary subset , let

,

note that this definition varies from the we defined in Lecture 2, because we will be discussing eigenfunctions without boundary conditions.  Now one defines .

Finally, we have the version of Cheeger’s inequality (proved by Alon and Milman in the discrete setting) for graphs without boundary.

Cheeger’s inequality: If is any graph with maximum degree , then

This follows fairly easy from the Dirichlet version of Cheeger’s inequality presented in Lecture 2.  Here’s a sketch:  Let satisfy , and suppose, without loss of generality, that has .  Define for and otherwise.  Then for , so we can plug into the Dirichlet version of Cheeger’s inequality with boundary conditions on .  For the full analysis, see this note which essentially follows this approach.  By examining the proof, note that one can find a subset with by a simple “sweep” algorithm:  Arrange the vertices so that , and output the best of the cuts .

So using the eigenvalue theorem of Spielman and Teng, along with Cheeger’s inequality, we can find a set with .  While this cut has the right Cheeger constant, it is not necessarily balanced (i.e. could be very small).  But one can apply this algorithm recursively, perhaps continually cutting small chunks off of the graph until a balanced cut is collected.  Refer to the Spielman-Teng paper for details.  A great open question is how one might use spectral information about to recover a balanced cut immediately, without the need for recursion.

Conformal mappings and circle packings

Now we focus on proving the bound for any planar graph .  A natural analog is to look at what happens for the Laplace-Beltrami operator for a Riemannian metric on the 2-sphere.  In fact, Hersch considered this problem almost 40 years ago and proved that , for any such Riemannian manifold .  His approach was to first use the uniformization theorem to get a conformal mapping from onto , and then try to pull-back the standard second eigenfunctions on (which are just the three coordinate projections).  Since the Dirichlet energy is conformally invariant in dimension 2, this almost works, except that the pulled-back map might not be orthogonal to the constant function.  To fix this, he has to post-process the initial conformal mapping with an appropriate Möbius transformation.

Unaware of Hersch’s work, Spielman and Teng derived eigenvalue bounds for planar graphs using the discrete analog of this approach:  Circle packings replace conformal mappings, and one still has to show the existence of an appropriate post-processing Möbius transformation.