Computation of highly regular nearby points
- We call a vector x/spl isin/R/sup n/ highly regular if it satisfies =0 for some short, non-zero integer vector m where <...> is the inner product. We present an algorithm which given x/spl isin/R/sup n/ and /spl alpha//spl isin/N finds a highly regular nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no short relation m~ of length less than /spl alpha//2 exists for points x~ within half the x'-distance from x. The integer relation m for x' is for random x up to an average factor 2/sup /spl alpha//2/ a shortest integer relation for x'. Our algorithm uses, for arbitrary real input x, at most O(n/sup 4/(n+log A)) many arithmetical operations on real numbers. If a is rational the algorithm operates on integers having at most O(n/sup 5/+n/sup 3/(log /spl alpha/)/sup 2/+log(/spl par/qx/spl par//sup 2/)) many bits where q is the common denominator for x.
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Carsten Rössner, Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12331 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Dokumentart: | Preprint |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 13.07.2005 |
| Jahr der Erstveröffentlichung: | 1995 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 13.07.2005 |
| Freies Schlagwort / Tag: | computational complexity; computational geometry; highly regular nearby points; inner product; integer vector; short integer relation |
| Bemerkung: | Preprint, später in: 3rd Israel Symposium on the Theory of Computing and Systems, 1995 |
| Quelle: | 3rd Israel Symposium on the Theory of Computing and Systems, 1995 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| HeBIS-PPN: | 224772023 |
| Institute: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
