Capital Area Theory Seminar

Consider the following scenario: A client sends a computational request to a "consulting" company on the internet, by specifying an input and a computational problem to be solved. The company then computes the answer and sends it back to the client. An obvious issue that arises, especially in the case that the company does not have a well established reputation, is: why should the client believe the answer to be correct? We consider the case when it is enough for the client to know that the answer is close to correct. We show that for a number of optimization functions, a very short dialogue between the client (the verifier) and the company (the prover) can convince the client of the approximate correctness of the answer. In fact, we give protocols for several optimization problems, in which the running time of the verifier is significantly less than the size of the input. In contrast, results such as IP=PSPACE, MIP=NEXPTIME and NP=PCP(log n,1) require a verifier which runs in Omega(n) time.

We give protocols for with sublinear time verifiers for approximate lower bounds on the solution quality of a subclass of linear programming problems referred to as fractional packing problems. We give protocols which allow a prover to convince a polylogarithmic time verifier of the existence of a large cut in a graph, a large matching in a graph or a small bin packing. Our results also apply to other optimization problems such as max flow and scheduling.

The protocols are very simple to describe, and the talk is essentially self-contained.

Joint work with Funda Ergun and S. Ravi Kumar.

Contact: Bill Gasarch.