Linear equations modulo 2 and the L1 diameter of convex bodies

Subhash Khot, Assaf Naor

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {aijk}ni, j, k=1 such that for all i, j, k zε {1,...,n} we have aijk = aikj = akji = ajik = akij = ajki and a iik = aijj = aiji = 0, computes a number Alg(A) which satisfies with probability at least 1/2, ω(√ log n/n t) - maxxzε{-1, 1}nni, j, k=1 aijkxixjxk ≤ Alg(A) ≤ max xzε{-1, 1}nni, j, k=1 aijkxixjxk. 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 maxxzε{-1, 1} nni, j, k=1 aijkx ixjxk 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 &Rn 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 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.

Original languageEnglish (US)
Pages (from-to)1448-1463
Number of pages16
JournalSIAM Journal on Computing
Volume38
Issue number4
DOIs
StatePublished - Nov 7 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Computational convex geometry
  • Grothendieck's inequality
  • Max-E3-Lin-2
  • Refutation of random SAT
  • Semidefinite programming

Fingerprint Dive into the research topics of 'Linear equations modulo 2 and the L<sub>1</sub> diameter of convex bodies'. Together they form a unique fingerprint.

  • Cite this