TY - CONF A1 - Rössner, Carsten A1 - Seifert, Jean-Pierre T1 - On the hardness of approximating shortest integer relations among rational numbers T2 - Computing: The Australasian Theory Symposium (CATS) '96 N2 - Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product = 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. KW - Approximation algorithm KW - Computational complexity KW - Integer relations KW - Label cover KW - NP-hard KW - Probabilistically checkable proofs Y1 - 2005 UR - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4239 UR - https://nbn-resolving.org/urn:nbn:de:hebis:30-12481 UR - http://www.mi.informatik.uni-frankfurt.de/research/papers.html ER -