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 [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=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 [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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages318-328
Number of pages11
DOIs
StatePublished - 2007
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

ASJC Scopus subject areas

  • Engineering(all)

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

    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). [4389503] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389503