Abstract:

 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 also 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.  In addition, our results 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.

 Most of this talk describes joint work with Funda Ergun and
 S. Ravi Kumar.  The rest of this talk describes joint work with
 Tugkan Batu and Patrick White.