Israel CS THEORY DAY

Open University of Israel

Division of Computer Science

 

Date: 17.3.08

Speaker: Assaf Naor

Title: Linear equations modulo 2 and the L_1 diameter of convex bodies.

Abstract:

In this talk we will present a connection between the problem of approximating efficiently the maximum number of satisfiable equations in an overdetermined system of linear equation modulo 2 (called Max-E3-Lin-2), and the problem of computing the diameter in the L_1 norm of a convex body in R^n. The reduction from the L_1 diameter problem is based on an application of Grothendieck's inequality. We will show that the L_1 diameter of a convex body in R^n which is given by an optimization oracle can be approximated in polynomial time up to a factor of O((n/log n)^{1/2}), improving the previous best known result due to Brieden, Gritzmann, Kannan, Klee, Lovasz and Simonovits.  This approximation factor is optimal. Using our new connection between the L_1 diameter problem and the Max-E3-Lin-2 problem, we will deduce the best known approximation algorithm for the advantage over random in Max-E3-Lin-2, improving a result of Hastad and Venkatesh. 

 Joint work with Subhash Khot.