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 zε {1,...,n} we have a_ijk = a_ikj = a_kji = a_jik = a_kij = a_jki and a _iik = a_ijj = a_iji = 0, computes a number Alg(A) which satisfies with probability at least 1/2, ω(√ log n/n t) - max_{xzε{-1, 1}}ⁿ ∑ⁿ_{i, j, k=1} a_ijkx_ix_jx_k ≤ Alg(A) ≤ max _{xzε{-1, 1}}ⁿ ∑ⁿ_{i, j, k=1} a_ijkx_ix_jx_k. On the other hand, we show via a simple reduction from a result of Håstad and Venkatesh [Random Structures Algorithms, 25 (2004), pp. 117-149] that under the assumption NP ⊈ DTIME(n^{(log n)O(1)}), for every zε > 0 there is no algorithm that approx imates max_{xzε{-1, 1}} ⁿ ∑ⁿ_{i, j, k=1} a_ijkx _ix_jx_k within a factor of 2 ^{(log n)}1-zε 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 &Rⁿ 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 et al. in [Mathematika, 48 (2001), pp. 63-105]. We apply our new algorithm to improve the algorithm of Håstad and Venkatesh for the Max-E3-Lin-2 problem. Given an overdetermined system ε of N linear equations modulo 2 in n ≤ N Boolean variables such that in each equation only three distinct variables appear, 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 obtained an algorithm which approximates this value up to a factor of O(√N). We obtain an 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.