On computations with integer division

Bettina Just; Friedhelm Meyer auf der Heide; Avi Wigderson

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1989)

  • Volume: 23, Issue: 1, page 101-111
  • ISSN: 0988-3754

How to cite

top

Just, Bettina, Meyer auf der Heide, Friedhelm, and Wigderson, Avi. "On computations with integer division." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 23.1 (1989): 101-111. <http://eudml.org/doc/92319>.

@article{Just1989,
author = {Just, Bettina, Meyer auf der Heide, Friedhelm, Wigderson, Avi},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {integer division; integer points in high-dimensional convex sets; computation trees; arithmetical progression},
language = {eng},
number = {1},
pages = {101-111},
publisher = {EDP-Sciences},
title = {On computations with integer division},
url = {http://eudml.org/doc/92319},
volume = {23},
year = {1989},
}

TY - JOUR
AU - Just, Bettina
AU - Meyer auf der Heide, Friedhelm
AU - Wigderson, Avi
TI - On computations with integer division
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1989
PB - EDP-Sciences
VL - 23
IS - 1
SP - 101
EP - 111
LA - eng
KW - integer division; integer points in high-dimensional convex sets; computation trees; arithmetical progression
UR - http://eudml.org/doc/92319
ER -

References

top
  1. 1. M. BEN OR, Lower bounds for Algebraic Computation Trees, Proc. 15th ACM STOC, 1983, pp. 80-86. 
  2. 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. Zbl0659.68051MR955578
  3. 3. J. W. S. CASSELS, An Introduction to the Geometry of Numbers, Springer, Berlin, 1959; second printing, 1971. Zbl0086.26203MR306130
  4. 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. Zbl0397.68045
  5. 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. Zbl0606.68033MR827729
  6. 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. Zbl0515.68037MR717993
  7. 7. H. W. Jr LENSTRA, Integer Programming with a Fixed Number of Variables, Report 81-03, Mathematisch Instituut, Amsterdam, 1983. MR727410
  8. 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. 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. Zbl0633.68031MR810344

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.