## Abstract

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {a_{ijk}}^{n}_{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}}^{n} ∑^{n}_{i, j, k=1} a_{ijk}x_{i}x_{j}x_{k} ≤ Alg(A) ≤ max _{xzε{-1, 1}}^{n} ∑^{n}_{i, j, k=1} a_{ijk}x_{i}x_{j}x_{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}} ^{n} ∑^{n}_{i, j, k=1} a_{ijk}x _{i}x_{j}x_{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^{n} with respect to the L_{1} 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 language | English (US) |
---|---|

Pages (from-to) | 1448-1463 |

Number of pages | 16 |

Journal | SIAM Journal on Computing |

Volume | 38 |

Issue number | 4 |

DOIs | |

State | Published - 2008 |

Externally published | Yes |

## 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