Bounding the sum of square roots via lattice reduction

Authors:
Qi Cheng, Xianmeng Meng, Celi Sun and Jiazhe Chen

Journal:
Math. Comp. **79** (2010), 1109-1122

MSC (2000):
Primary 11Y40

DOI:
https://doi.org/10.1090/S0025-5718-09-02304-7

Published electronically:
September 30, 2009

MathSciNet review:
2600558

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let and be positive integers. Define to be the minimum positive value of

**1.**C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.

A strong and easily computable separation bound for arithmetic expressions involving radicals.*Algorithmica*, 27(1):87-99, 2000. MR**1748595 (2001h:68148)****2.**Qi Cheng.

On comparing sums of square roots of small integers.

In*Proc. of 31st International Symposium on Mathematical Foundations of Computer Science (MFCS)*, volume 4162 of*Lecture Notes in Computer Science*, 2006. MR**2298182 (2007m:68256)****3.**Noam D. Elkies.

Rational points near curves and small nonzero via lattice reduction.

In W. Bosma, editor,*Proceedings of ANTS-4*, volume 1838 of*Lecture Notes in Computer Science*, pages 33-63, 2000. MR**1850598 (2002g:11035)****4.**Kousha Etessami and Mihalis Yannakakis.

On the complexity of Nash equilibria and other fixed points.

In*Proceedings of the 48th FOCS*, pages 113-123, 2007.**5.**M. Garey, R.L. Graham, and D.S. Johnson.

Some NP-complete geometric problems.

In*Proc. ACM Symp. Theory Comp.*, pages 10-21, 1976. MR**0468310 (57:8146)****6.**Subhash Khot.

Hardness of approximating the shortest vector problem in lattices.

In*Proc. th IEEE Symp. on Foundations of Comp. Science*, 2004. MR**2176563 (2006h:68051)****7.**Daniele Micciancio and Shafi Goldwasser.*Complexity of Lattice Problems: A Cryptographic Perspective*.

Kluwer Academic Publishers, 2002. MR**2042139 (2004m:94067)****8.**Francesco Pappalardi.

A survey on freeness.

In*Proceeding of the Conference in Analytic Number Theory in Honor of Prof. Subbarao*, number 1 in Ramanujan Math. Soc. Lect. Notes Ser., pages 71-88, 2002. MR**2131677 (2005k:11194)****9.**Jianbo Qian and Cao An Wang.

How much precision is needed to compare two sums of square roots of integers?*Inform Process. Lett.*, 100(5):194-198, 2006. MR**2253248 (2008f:65040)****10.**C. P. Schnorr.

A hierarchy of polynomial time lattice basis reduction algorithms.*Theoretical Computer Science*, 53(2-3):201-224, 1987. MR**918090 (89h:11085)****11.**Prasoon Tiwari.

A problem that is easier to solve on the unit-cost algebraic RAM.*Journal of Complexity*, 8(4):393-397, 1992. MR**1195259 (94a:68056)**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y40

Retrieve articles in all journals with MSC (2000): 11Y40

Additional Information

**Qi Cheng**

Affiliation:
School of Computer Science, The University of Oklahoma, Norman, Oklahoma 73019

Email:
qcheng@cs.ou.edu

**Xianmeng Meng**

Affiliation:
Lab of Cryptographic Technology and Information Security, Shandong University, Jinan 250100, People’s Republic of China

**Celi Sun**

Affiliation:
School of Computer Science, The University of Oklahoma, Norman, Oklahoma 73019

Email:
scl@cs.ou.edu

**Jiazhe Chen**

Affiliation:
Lab of Cryptographic Technology and Information Security, Shandong University, Jinan 250100, People’s Republic of China

DOI:
https://doi.org/10.1090/S0025-5718-09-02304-7

Received by editor(s):
January 5, 2009

Received by editor(s) in revised form:
May 1, 2009

Published electronically:
September 30, 2009

Additional Notes:
This research is partially supported by NSF Career Award CCR-0237845 of USA and by Project 973 (no: 2007CB807903 and no: 2007CB807902) of China.

Article copyright:
© Copyright 2009
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.