𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower Bounds for the Complexity of Functions in a Realistic RAM Model

✍ Scribed by Nader H. Bshouty

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
127 KB
Volume
32
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

This paper develops a new technique that finds almost tight lower bounds for the complexity of programs that compute or approximate functions in a realistic RAM model. The nonuniform realistic RAM model is a model that uses the arithmetic Γ„ 4 operations q, y, = , the standard bit operation Shift, Rotate by one bit, bitwise AND, OR, XOR, NOT, comparisons, and indirect addressing. The functions considered here are integer division, modulo, square root, gcd, and logarithms. The complexity of multiplication is also studied in the above model when it does not have the = operation. We also show that if we add integer division to the realistic RAM model with infinite word size them no nontrivial lower bound can be proven. Our results can be extended to both probabilistic and nondeterministic models.

πŸ“œ SIMILAR VOLUMES

On a Lower-Bound for the Absolute Value
On a Lower-Bound for the Absolute Value of a Polynomial of Several Complex Variables
✍ B. Paneah πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 268 KB

For an arbitrary polynomial \(P\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) in complex space \(\mathbb{C}^{n}\) we describe a set of nonnegative multi-indices \(\alpha=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\right)\) such that for any \(n\)-tuple \(\delta=\left(\delta_{1}, \delta_{2}, \ldots,

A Lower Bound in an Approximation Proble
A Lower Bound in an Approximation Problem Involving the Zeros of the Riemann Zeta Function
✍ Jean-FranΓ§ois Burnol πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 165 KB

We slightly improve the lower bound of B! a aez-Duarte, Balazard, Landreau and Saias in the Nyman-Beurling formulation of the Riemann Hypothesis as an approximation problem. We construct Hilbert space vectors which could prove useful in the context of the so-called ''Hilbert-P ! o olya idea''.

A superlinear lower bound for the size o
A superlinear lower bound for the size of a critical set in a latin square
✍ Nicholas J. Cavenagh πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 157 KB πŸ‘ 1 views

## Abstract A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let __scs__(__n__) denote the smallest possible size of a critical set in a latin square of order __n__. We show that for all __n__, $scs(n)\geq n\lfloo