✦ LIBER ✦

Maximizing a lower bound on the computational complexity

✍ Scribed by Georg Gati

Publisher: Elsevier Science
Year: 1982
Tongue: English
Weight: 294 KB
Volume: 4
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(82)90037-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A lower bound on Voronoi diagram complex

A lower bound on Voronoi diagram complexity

✍ Boris Aronov 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 49 KB

A lower bound on the computational compl

A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

✍ Eric Goles; Marcos Kiwi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 483 KB

A linear lower bound on the unbounded er

A linear lower bound on the unbounded error probabilistic communication complexity

✍ Jürgen Forster 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 187 KB

The main mathematical result of this paper may be stated as follows: Given a matrix MAfÀ1; 1g nÂn and any matrix MAR nÂn such that signð Mi;j Þ ¼ M i;j for all i; j; then rankð MÞXn=jjMjj: Here jjMjj denotes the spectral norm of the matrix M: This implies a general lower bound on the complexity of

A 3n-lower bound on the network complexi

A 3n-lower bound on the network complexity of Boolean functions

✍ C.P. Schnorr 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 972 KB

How to derive a quantum complexity lower

How to derive a quantum complexity lower bound

✍ Tetsuro Nishino 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 1 views

Complexity Lower Bounds for Approximatio

Complexity Lower Bounds for Approximation Algebraic Computation Trees

✍ Felipe Cucker; Dima Grigoriev 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 159 KB

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.