On computations with integer division
Just, Bettina ; Meyer auf der Heide, Friedhelm ; Wigderson, Avi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989), p. 101-111 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1989-01-01
@article{ITA_1989__23_1_101_0,
     author = {Just, Bettina and Meyer auf der Heide, Friedhelm and Wigderson, Avi},
     title = {On computations with integer division},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {23},
     year = {1989},
     pages = {101-111},
     mrnumber = {990070},
     zbl = {0665.68027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1989__23_1_101_0}
}

Just, Bettina; Meyer auf der Heide, Friedhelm; Wigderson, Avi. On computations with integer division. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) pp. 101-111. http://gdmltest.u-ga.fr/item/ITA_1989__23_1_101_0/

1. M. Ben Or, Lower bounds for Algebraic Computation Trees, Proc. 15th ACM STOC, 1983, pp. 80-86.

2. L. Babai, B. Just and F. Meyer Auf Der Heide, On the Limits of Computations with the Floor Functions, Information and Computation, 78 (2), 1988, pp. 99-107. | MR 955578 | Zbl 0659.68051

3. J. W. S. Cassels, An Introduction to the Geometry of Numbers, Springer, Berlin, 1959; second printing, 1971. | MR 306130 | Zbl 0086.26203

4. D. Dobkin and R. Lipton, A Lower Bound of 1/2n2 on Linear Search Programs for the Knapsack Problem, J..C.S.S., Vol. 16, 1975, pp. 417-421. | Zbl 0397.68045

5. J. Hastad, B. Just,J. Lagarias and C. P. Schnorr, Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers, Proc. STACS, 1986, pp. 105-118. | MR 827729 | Zbl 0606.68033

6. P. Klein and F. Meyer Auf Der Heide, A Lower Bound for the Knapsack Problem on Random Access Machines, Act. Inf., Vol. 19, 1983, pp. 385-395. | MR 717993 | Zbl 0515.68037

7. H. W. Jr Lenstra, Integer Programming with a Fixed Number of Variables, Report 81-03, Mathematisch Instituut, Amsterdam, 1983. | MR 727410

8. J. C. Lagarias, H. W. Jr. Lenstra and C. P. Schnorr, Karkine-Zolotareff Bases and Successive Minima of a Latice and its Reciprocla Lattice, preprint 1986.

9. F. Meyer Auf Der Heide, Lower Bounds for Solving Linear Diophantine equations on Random Acces Machines, J.ACM., Vol. 32 (4), 1985, pp. 929-937. | MR 810344 | Zbl 0633.68031