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 &#8467;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 &#8722; 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 &#8467;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 &#8467;infinity-shortest integer solution for a homogeneous linear system of equations over Q.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Carsten Rössner, Jean-Pierre Seifert
Parent Title (English):Computing: The Australasian Theory Symposium (CATS) '96
Document Type:Conference Proceeding
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
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht