# Linear equations modulo 2 and the L1 diameter of convex bodies

Subhash Khot, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

### Abstract

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {aijk}i,j,kn=1 such that for all i, j, k ε {1,...,n} we have aijk = aikj = a kji=ajik=ajkiand aiik = a ijj = aiji = 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  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=1na ijkxixjxk 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 ℝn with respect to the L1 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 . We apply our new algorithm to improve the algorithm of Hâstad and Venkatesh  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  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.

Original language English (US) Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 318-328 11 https://doi.org/10.1109/FOCS.2007.4389503 Published - 2007 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United StatesDuration: Oct 20 2007 → Oct 23 2007

### Publication series

Name Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 0272-5428

### Other

Other 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 United States Providence, RI 10/20/07 → 10/23/07

### ASJC Scopus subject areas

• Engineering(all)

• ## Cite this

Khot, S., & Naor, A. (2007). Linear equations modulo 2 and the L1 diameter of convex bodies. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 (pp. 318-328).  (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389503