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.