The Geomblog

This is where we left off last time:

If a set of inputs parametrized by d parameters is accepted in the linear PRAM model with p processors in t time, then there is a way of partitioning using hyperplanes, so that each cell of the resulting arrangement can be labelled 0 or 1 so that an input z is accepted iff it lies in a cell labelled with a 1.

The above lemma describes the geometric structure induced by an efficient computation on a linear PRAM. Now, we'll see how a high parametric complexity problem breaks this structure.
We will do this by demonstrating that such a problem has too many accepting and non-accepting inputs close to each other to allow for such a cell labelling with these few hyperplanes.


We start with some parametrized problem (with parameter ) with cardinality n and bitsize . Remember that the bitsize refers to the maximum complexity of the coefficients of expressions involving . Let the parametric complexity of this problem (as we defined earlier) be . For technical reasons, we will require that the problem under consideration be homogeneous (scaling values by a constant multiplies OPT by the same value); this does not change anything, since this is true for problems like min-cost flow and max-flow.

Each numeric parameter in the input can be expressed as some , and without loss of generality we will assume that u and v are integers. We will actually need all parameters to be integral, so thinking of as the rational , we can rewrite all such parameters in the form , yielding a new instance with the same combinatorial structure (again, homogeneity makes things easy).

We now have a two parameter system that describes an input to the problem. A third parameter will describe the threshold for this (optimization) problem. Specifically, the goal will be to decide whether the value obtained is at least . Let a be some "large enough constant", and consider all inputs where the threshold has bitsize at most and each parameter generated from has bitsize at most .

This is a three-parameter system (d=3). We can therefore translate the structural result at the top of the post into a concrete statement regarding all problems parametrized in this manner.

Let be some constant. Set the desired time bound , and let the number of processors . Then a linear PRAM algorithm that works on this parametrized input in the specified resource bounds induces a partition of by at most planes, where each face can be labelled as specified above.

There's a more general version of this theorem that makes the tradeoff between time and processors more explicit: I'll skip that for now. Also note that the "5" in the exponent is somewhat arbitrary: it's just chosen to make things work unambiguously.


We'll now encounter an ingenious geometric representation of the set of feasible inputs for the parametric problem. Let be the optimal function value as a function of the input P, and let G be its function graph. An input I to the problem is parametrized by the three parameters , and is feasible when , which can be restated (remembering that ) as the condition (dividing through by and using homogeneity. We will also assume wlog that is positive)

At this point, a geometer will look at expressions like , and immediately see a projective plane. And that's what happens ! We can think of the space of possible parameter values as inhabiting a projective space, with playing the role of the z-direction (in which case the action, as it were, happens on the z=1 plane).
The parameters define a ray in 3D that intersects the z=1 plane in the point (you should look at Figure 4.1 in the paper to help visualize what's going on).

What then happens to the function graph G ? We can think of G as lying in the affine plane z=1 (parametrized by ), and fan(G) as the set of all points in that project onto $G$ (via the projective transform). We can now translate the feasibility condition into the geometric condition that the point lies "below" fan(G) in the axis.

It helps to think of as an ordinary function in the affine plane, in which case the space of feasible values is the set of all points that project to points in the plane below its graph. In other words, all integer points in are labelled as 1 if they lie below fan(G) in the direction.

In the next installment, we'll show that any arrangement of few hyperplanes in this space will not be able to capture all the 0 and 1 points correctly.

Taken together, the P vs NC paper is quite intimidating in its size and scope. And yet, when it's cut down to bite-sized blogging chunks, the pieces seem to follow inexorably in a manner that leaves one asking, 'how else could it have been'. There's the key inspiration of using parametric complexity, the magic trick we'll see more of today. But the rest of it uses the kind of geometric arguments that are familiar to anyone who's read papers on the complexity of arrangements. Make no mistake: taking care of issues of bit complexity requires delicate arguments. But the main thrust of the approach is surprisingly easy to explain, ONCE we've accepted the magic trick.

In this post and the next, we'll begin to see glimmers of the WHY for the parametric argument. In brief, using parametric complexity allows us to navigate an affine subspace of the space of all possible inputs, and then we let geometry take over and guide us.

We're close to seeing the main killer argument at the heart of the paper. But as with many arguments, it's easier if we look at a skeleton argument applied to a somewhat simpler case. We already saw a toy example of this argument, and now we'll move to a more nontrivial model, that of linear PRAMs.

In the first post, we defined a linear PRAM as a PRAM-without-bitops in which all multiplications are by a constant. We'll see a slightly stronger lower bound for computations in this model. Specifically, we will show that for a problem with parametric complexity and bitsize , there exists a large enough constant b such that the problem cannot be solved on a linear PRAM with p processors in time . This generalizes the bound that will hold for the stronger model: namely, time with processors.

Substituting what we've already seen for the parametric complexity of max-flow, we recover a lower bound of time using p processors, for an n-node network.

Notes:

• For clarity, I'm skipping over the specification of bitlengths: these will fold in later, but throwing in all these numbers right now confuses the flow.
  
• As before, the lower bound applies for approximations and randomization: how this happens will be discussed later on.
  

The high-level proof strategy first requires us to bound the number of possible branchings of an algorithm in this model, and then requires us to describe the "cells" of these branchings in some geometric manner. As we did earlier, we'll say that two inputs x, x' are t-equivalent if the machine executes the same set of instructions on x and x' for the first t steps of the computation.
This defines an equivalence relation, and our goal will be to estimate the number of equivalence classes in this relation (as a function of t).

Now let's introduce the parametrization. Suppose that each input x is a function of d parameters , where each particular input variable is expressed as a linear function of the parameters. We'll further assume that these linear forms are integral, and the parameters range over integer values with some bounded bitlength.

The partitioning of the inputs x into equivalence classes induces a partitioning of the parameters in the obvious way (two parameter vectors z, z' are t-equivalent if the corresponding x, x' are). Let denote the number of t-equivalent classes in the parameter space. The main result we can show now is that:

For all t, is bounded by

Here's the proof argument (and for those of you who've waded through parametric search, this will be familiar): First of all, remember that since all operations are linear (since one term of each multiplication is a constant), each arithmetic operation is some linear function of the input. From this, and the assumption that memory pointers are not functions of the input (this is the circuit view of the computation), it follows that the contents of each memory location are a linear function of the equivalence class the input lies in, and the time t.

Now imagine simulating the execution of the algorithm on an as-yet unspecified parameter vector z (as we do in parametric search). What this means is that arithmetic operations are linear forms defined over the symbolic value of the parameter. When a branch occurs, the branch outcome is determined by comparing two linear forms, which reduces to testing the sign of a linear expression. Let's take some z in a fixed t-equivalence class C. From the above remarks, each branch involves testing at most p linear forms on z, each of which can be viewed as a hyperplane in . If we now look at the arrangement of these hyperplanes, then each cell represents a fixed set of decisions for the branch outcomes. By standard arguments, the complexity of this arrangement is .

Now how does this arrangement evolve at the next time step ? Clearly, any single piece of the equivalence class C can be split by the arrangement into smaller pieces, based on decisions that are made at the next time step. But from above, there are only such splits possible. Therefore, , yielding the desired bound.

A corollary is that if we track any particular t-equivalence class, it is split by at most pt linear forms (one for each time step and each processor), and so it is sufficient to check the signs of these forms to determine whether any particular z belongs to C.

Finally, taking a union over all possible equivalence classes, we get the following result:

If a set of inputs parametrized by d parameters is accepted in the linear PRAM model with p processors in t time, then there is a way of partitioning using hyperplanes, so that each cell of the resulting arrangement can be labelled 0 or 1 so that an input z is accepted iff it lies in a cell labelled with a 1.

In the next part of this argument, we will show that a problem with high parametric complexity cannot be represented this way: that is, there must be some cell that contains inputs in the language, and inputs not in the language.