Lower bounds for computations with the floor operation

Yishay Mansour; Baruch Schieber; Prasoon Tiwari

doi:10.1137/0220020

Lower bounds for computations with the floor operation

Yishay Mansour
, Baruch Schieber
, Prasoon Tiwari

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

A general lower bound technique is developed for computation trees with various arithmetic operations and constants {0, 1}, for functions that have as their input a a single n-bit integer. The technique applies to many natural functions. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with the given operations that solves the problem.

Original language	English (US)
Pages (from-to)	315-327
Number of pages	13
Journal	SIAM Journal on Computing
Volume	20
Issue number	2
DOIs	https://doi.org/10.1137/0220020
State	Published - 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0220020

Cite this

@article{864da3d695d249e49cb0e0f53ac054bf,

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

abstract = "A general lower bound technique is developed for computation trees with various arithmetic operations and constants \{0, 1\}, for functions that have as their input a a single n-bit integer. The technique applies to many natural functions. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with the given operations that solves the problem.",

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

year = "1991",

doi = "10.1137/0220020",

language = "English (US)",

volume = "20",

pages = "315--327",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Lower bounds for computations with the floor operation

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1991

Y1 - 1991

N2 - A general lower bound technique is developed for computation trees with various arithmetic operations and constants {0, 1}, for functions that have as their input a a single n-bit integer. The technique applies to many natural functions. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with the given operations that solves the problem.

AB - A general lower bound technique is developed for computation trees with various arithmetic operations and constants {0, 1}, for functions that have as their input a a single n-bit integer. The technique applies to many natural functions. The arguments are then extended to obtain the same lower bounds on the time complexity of any RAM program with the given operations that solves the problem.

UR - https://www.scopus.com/pages/publications/0026140431

UR - https://www.scopus.com/pages/publications/0026140431#tab=citedBy

U2 - 10.1137/0220020

DO - 10.1137/0220020

M3 - Article

AN - SCOPUS:0026140431

SN - 0097-5397

VL - 20

SP - 315

EP - 327

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Lower bounds for computations with the floor operation

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this