Linear equations modulo 2 and the L₁ diameter of convex bodies

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {a_ijk}_i,j,kⁿ=1 such that for all i, j, k ε {1,...,n} we have a_ijk = a_ikj = a _kji=a_jik=a_jkiand a_iik = a _ijj = a_iji = 0 computes a number Alg(A) which satisfies with probability at least 1/2, equation present On the other hand, we show via a simple reduction from a result of Håstad and Venkatesh [22] that under the assumption NP ⊈ DTIME (n^{(log n)O(1)}) for every ε > 0 there is no algorithm that approximates max _{xε{-1, 1}n}Σ_i,j,k=1ⁿa _ijkx_ix_jx_k within a factor of 2( ^{log n)1-ε} in time 2^{(log n)O(1)}. Our algorithm is based on a reduction to the problem of computing the diameter of a convex body in ℝⁿ with respect to the L₁ norm. We show that it is possible to do so up to a multiplicative error of O (√n/log n), while no randomized polynomial time algorithm can achieve accuracy o (√n/log n). This resolves a question posed by Brieden, Gritzmann, Kannan, Klee, Lovász and Simonovits in [10]. We apply our new algorithm to improve the algorithm of Hâstad and Venkatesh [22] for the Max-E3-Lin-2 problem. Given an over-determined system S of N linear equations modulo 2 in n ≤ N 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 ε minus N/2 (i.e. we subtract the expected number of satisfied equations in a random assignment). Håstad and Venkatesh [22] obtained an algorithm which approximates this value up to a factor of O (√N). We obtain a O (√n/log n) 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.