✦ LIBER ✦

A nonlinear lower bound on the practical combinational complexity

✍ Scribed by Xaver Gubáš; Juraj Hromkovič; Juraj Waczulík

Book ID: 107948805
Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 558 KB
Volume: 143
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(94)00269-o

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximizing a lower bound on the computat

Maximizing a lower bound on the computational complexity

✍ Georg Gati 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 294 KB

A lower bound on Voronoi diagram complex

A lower bound on Voronoi diagram complexity

✍ Boris Aronov 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 49 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

Lower Bounds on the Multiparty Communica

Lower Bounds on the Multiparty Communication Complexity

✍ Pavol Ďuriš; José D.P. Rolim 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 236 KB

A new lower bound on the monotone networ

A new lower bound on the monotone network complexity of Boolean sums

✍ Ingo Wegener 📂 Article 📅 1980 🏛 Springer-Verlag 🌐 English ⚖ 282 KB