Lower bounds for computations with the floor operation

Yishay Mansour; Baruch Schieber; Prasoon Tiwari

doi:10.1007/BFb0035783

Lower bounds for computations with the floor operation

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

We prove an Ω(√log n) lower bound on the depth of any decision tree with operations {+, −, *, /, ⌊·⌋, <}, that decides whether an integer is a perfect square, for any n-bit integer. We then extend the arguments to obtain the same lower bound on the time complexity of any RAM program with operations {+, −, *, /, ⌊·⌋, <} that solves the problem. Our proof technique can be used to derive lower bounds for many other problems. Another related result is described in a companion paper ([IBM Research Report RC 14271], [Proceedings of the 29th FOCS]).

Original language	American English
Title of host publication	Automata, Languages and Programming - 16th International Colloquium, Proceedings
Editors	Mariangiola Dezani-Ciancaglini, Simonetta Ronchi Della Rocca, Giorgio Ausiello
Publisher	Springer Verlag
Pages	559-573
Number of pages	15
ISBN (Print)	9783540513711
DOIs	https://doi.org/10.1007/BFb0035783
State	Published - 1989
Externally published	Yes
Event	16th International Colloquium on Automata, Languages and Programming, 1989 - Stresa, Italy Duration: Jul 11 1989 → Jul 15 1989

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	372 LNCS

Conference

Conference	16th International Colloquium on Automata, Languages and Programming, 1989
Country/Territory	Italy
City	Stresa
Period	7/11/89 → 7/15/89

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0035783

Cite this

Mansour, Y., Schieber, B., & Tiwari, P. (1989). Lower bounds for computations with the floor operation. In M. Dezani-Ciancaglini, S. R. Della Rocca, & G. Ausiello (Eds.), Automata, Languages and Programming - 16th International Colloquium, Proceedings (pp. 559-573). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 372 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0035783

Mansour, Yishay ; Schieber, Baruch ; Tiwari, Prasoon. / Lower bounds for computations with the floor operation. Automata, Languages and Programming - 16th International Colloquium, Proceedings. editor / Mariangiola Dezani-Ciancaglini ; Simonetta Ronchi Della Rocca ; Giorgio Ausiello. Springer Verlag, 1989. pp. 559-573 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{acf67d9d91254aed80c53347b0c76b90,

title = "Lower bounds for computations with the floor operation",

abstract = "We prove an Ω(√log n) lower bound on the depth of any decision tree with operations {+, −, *, /, ⌊·⌋, <}, that decides whether an integer is a perfect square, for any n-bit integer. We then extend the arguments to obtain the same lower bound on the time complexity of any RAM program with operations {+, −, *, /, ⌊·⌋, <} that solves the problem. Our proof technique can be used to derive lower bounds for many other problems. Another related result is described in a companion paper ([IBM Research Report RC 14271], [Proceedings of the 29th FOCS]).",

author = "Yishay Mansour and Baruch Schieber and Prasoon Tiwari",

note = "Publisher Copyright: {\textcopyright} 1989, Springer-Verlag.; 16th International Colloquium on Automata, Languages and Programming, 1989 ; Conference date: 11-07-1989 Through 15-07-1989",

year = "1989",

doi = "10.1007/BFb0035783",

language = "American English",

isbn = "9783540513711",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "559--573",

editor = "Mariangiola Dezani-Ciancaglini and {Della Rocca}, {Simonetta Ronchi} and Giorgio Ausiello",

booktitle = "Automata, Languages and Programming - 16th International Colloquium, Proceedings",

address = "Germany",

}

Mansour, Y, Schieber, B & Tiwari, P 1989, Lower bounds for computations with the floor operation. in M Dezani-Ciancaglini, SR Della Rocca & G Ausiello (eds), Automata, Languages and Programming - 16th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 372 LNCS, Springer Verlag, pp. 559-573, 16th International Colloquium on Automata, Languages and Programming, 1989, Stresa, Italy, 7/11/89. https://doi.org/10.1007/BFb0035783

Lower bounds for computations with the floor operation. / Mansour, Yishay; Schieber, Baruch; Tiwari, Prasoon.
Automata, Languages and Programming - 16th International Colloquium, Proceedings. ed. / Mariangiola Dezani-Ciancaglini; Simonetta Ronchi Della Rocca; Giorgio Ausiello. Springer Verlag, 1989. p. 559-573 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 372 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Lower bounds for computations with the floor operation

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1989

Y1 - 1989

N2 - We prove an Ω(√log n) lower bound on the depth of any decision tree with operations {+, −, *, /, ⌊·⌋, <}, that decides whether an integer is a perfect square, for any n-bit integer. We then extend the arguments to obtain the same lower bound on the time complexity of any RAM program with operations {+, −, *, /, ⌊·⌋, <} that solves the problem. Our proof technique can be used to derive lower bounds for many other problems. Another related result is described in a companion paper ([IBM Research Report RC 14271], [Proceedings of the 29th FOCS]).

AB - We prove an Ω(√log n) lower bound on the depth of any decision tree with operations {+, −, *, /, ⌊·⌋, <}, that decides whether an integer is a perfect square, for any n-bit integer. We then extend the arguments to obtain the same lower bound on the time complexity of any RAM program with operations {+, −, *, /, ⌊·⌋, <} that solves the problem. Our proof technique can be used to derive lower bounds for many other problems. Another related result is described in a companion paper ([IBM Research Report RC 14271], [Proceedings of the 29th FOCS]).

UR - http://www.scopus.com/inward/record.url?scp=84911480524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84911480524&partnerID=8YFLogxK

U2 - 10.1007/BFb0035783

DO - 10.1007/BFb0035783

M3 - Conference contribution

SN - 9783540513711

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 559

EP - 573

BT - Automata, Languages and Programming - 16th International Colloquium, Proceedings

A2 - Dezani-Ciancaglini, Mariangiola

A2 - Della Rocca, Simonetta Ronchi

A2 - Ausiello, Giorgio

PB - Springer Verlag

T2 - 16th International Colloquium on Automata, Languages and Programming, 1989

Y2 - 11 July 1989 through 15 July 1989

ER -

Mansour Y, Schieber B, Tiwari P. Lower bounds for computations with the floor operation. In Dezani-Ciancaglini M, Della Rocca SR, Ausiello G, editors, Automata, Languages and Programming - 16th International Colloquium, Proceedings. Springer Verlag. 1989. p. 559-573. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0035783

Lower bounds for computations with the floor operation

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this