__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.**