## Abstract

We design a randomized polynomial time algorithm which, given a 3-tensor of real numbers A = {a_{ijk}}_{i,j,k}^{n}=1 such that for all i, j, k ε {1,...,n} we have a_{ijk} = a_{ikj} = a _{kji}=a_{jik}=a_{jki}and a_{iik} = a _{ijj} = a_{iji} = 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=1}^{n}a _{ijk}x_{i}x_{j}x_{k} 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 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, 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 |

Pages | 318-328 |

Number of pages | 11 |

DOIs | |

State | Published - 2007 |

Event | 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States Duration: Oct 20 2007 → Oct 23 2007 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

Other | 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 |
---|---|

Country | United States |

City | Providence, RI |

Period | 10/20/07 → 10/23/07 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)