## On the hardness of approximating shortest integer relations among rational numbers

- Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time O(npoly(log n)), the ℓinfinity-shortest integer relation for a given vector x small epsilon, Greek Qn cannot be approximated in polynomial time within a factor of 2log0.5 − small gamma, Greekn, where small gamma, Greek is an arbitrarily small positive constant. This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known L3-algorithm approximates for a vector x small epsilon, Greek Qn the ℓ2-shortest integer relation within a factor of 2n/2 in polynomial time. Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems. The same inapproximability result is valid for finding the ℓinfinity-shortest integer solution for a homogeneous linear system of equations over Q.

Author: | Carsten Rössner, Jean-Pierre Seifert |
---|---|

URN: | urn:nbn:de:hebis:30-12481 |

URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |

Parent Title (English): | Computing: The Australasian Theory Symposium (CATS) '96 |

Document Type: | Conference Proceeding |

Language: | English |

Date of Publication (online): | 2005/07/19 |

Year of first Publication: | 1996 |

Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |

Release Date: | 2005/07/19 |

Tag: | Approximation algorithm; Computational complexity; Integer relations; Label cover; NP-hard; Probabilistically checkable proofs |

Page Number: | 7 |

Source: | Computing: The Australasian Theory Symposium (CATS) '96 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |

HeBIS-PPN: | 22477851X |

Institutes: | Informatik und Mathematik / Mathematik |

Informatik und Mathematik / Informatik | |

Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |

Licence (German): | Deutsches Urheberrecht |