### Abstract

The classical Grothendieck constant, denoted K _{G}, is equal to the integrality gap of the natural semi definite relaxation of the problem of computing (Equation Presented), a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that K _{G} ≤ π/2 log(1+√2) and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that K _{G} < π/2 log(1+√2)-ε _{0} for an explicit constant ε _{0} > 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ ^{2} in order to round the projected vectors, beat the random hyper plane technique, contrary to Krivine's long-standing conjecture.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 |

Pages | 453-462 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2011 |

Externally published | Yes |

Event | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States Duration: Oct 22 2011 → Oct 25 2011 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

Other | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 |
---|---|

Country | United States |

City | Palm Springs, CA |

Period | 10/22/11 → 10/25/11 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Cite this

*Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011*(pp. 453-462). [6108206] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2011.77