Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A={a ijk } ij,k=1 n such that for all i,j,kisin{1,...,n} we have a ijk =a ikj =a kji =a jik =a kij =a kji and a iik =a ijj =a iji =0, computes a number Alg(A) which satisfies with probability at least 1/2, Omega(radic(logn/n))ldrmax xisin{-1,1} n Sigma i,j,k=1 n a ijk x i x j x k lesAlg(A)lesmax xisin{-1,1} n Sigma i,j,k=1 n a ijk x i x j x k . On the other hand, we show via a simple reduction from a result of Hastad and Venkatesh that under the assumption NPnsubeDTIME(n (logn) O(1) ),for every epsiv>0 there is no algorithm that approximates max xisin{-1,1} n Sigma i,j,k=1 n a ijk x i x j x k within a factor of 2(logn) t-epsiv in time 2 (logn) O(1) . Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in R n with respect to the L 1 norm. We show that it is possible to do so up to a multiplicative error of O(radic(n/logn)), while no randomized polynomial time algorithm can achieve accuracy O(radic(n/logn)). This resolves a question posed by Brieden, Gritzmann, Kantian, Klee, Lovasz and Simonos. We apply our new algorithm improve the algorithm of Hastad and Venkatesh or the Max-E3-Lin-2 problem. Given an over-determined system epsiv of N linear equations modulo 2 in nlesN Boolean variables, such that in each equation appear only three distinct variables, the goal is to approximate in polynomial time the maximum number of satisfiable equations in epsiv minus N/2 (i.e. we subtract the expected number of satisfied equations in a random assignment). Hastad and Venkatesh obtained an algorithm which approximates this value up to a factor of O(radicN). We obtain a O(radic(n/logn)) approximation algorithm. By relating this problem to the refutation problem for random 3-CNF formulas we give evidence that obtaining a significant improvement over this approximation factor is likely to be difficult.