Israel CS THEORY DAY
Open University of
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.