Ravi Kannan (Yale University):
Random sub-problems of a given problem

We consider a class of problems typcial of which is the MAX-r-SAT prob- lem of satisfying as many clauses as possible among given clauses with r literals each (r fixed). Our main result that if we pick at random a small subset of the variables, the answer to the sub-problem consisting of only the clauses involving the picked variables gives us an estimate of the answer to the whole problem.

Our methods are in a sense purely ``linear algebraic''. Our starting point is the formulation of the problem by means of r dimensional arrays of reals and a simple approximation of these arrays by the sum of ``rank 1'' arrays. A central result we prove and use is an upper bound on a certain norm of a random sub-array of an r dimensional array in terms of the same norm of the whole array. The norm is chosen to model these combinatorial problems.

Joint work with N. Alon, F.W. dela Vega and M. Karpinski