Speaker: Assaf Naor, Courant Institute of Mathematical Sciences
Time: Thu Oct 11, 2:15pm, WWH-1314
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.