###
On the Hardness of Approximating Shortest Integer Relations
among Rational Numbers

Carsten R\H{o}ssner

Department of Mathematical Computer Science,
University of Frankfurt,
P.O. Box 11 19 32,
60054 Frankfurt on the Main,
Germany

roessner@cs.uni-frankfurt.de

Jean-Pierre Seifert

Department of Mathematical Computer Science,
University of Frankfurt,
P.O. Box 11 19 32,
60054 Frankfurt on the Main,
Germany

seifert@cs.uni-frankfurt.de

####
Given $x \in {\Bbb{R}}^n$ an integer relation for $x$
is a non-trivial vector $m \in {\Bbb{Z}}^n$
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(n^{poly(\log n)})$,
the $\ell_{\infty}$-shortest integer relation for a given
vector $x \in {\Bbb{Q}}^n$
cannot be approximated in polynomial time
within a factor of $2^{\log^{0.5 - \gamma} n}$,
where $\gamma$ 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 $L^3$-algorithm approximates
for a vector $x \in {\Bbb{Q}}^n$
the $\ell_{2}$-shortest integer relation
within a factor of $2^{n/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 $\ell_{\infty}$-shortest integer solution
for a homogeneous linear system of equations over ${\Bbb{Q}}$.

Conference Home Page