A DIRECT VERSION OF SHAMIR AND SNIR LOWER BOUNDS ON MONOTONE CIRCUIT DEPTH

Authors
TIWARI P TOMPA M
Citation
P. Tiwari et M. Tompa, A DIRECT VERSION OF SHAMIR AND SNIR LOWER BOUNDS ON MONOTONE CIRCUIT DEPTH, Information processing letters, 49(5), 1994, pp. 243-248
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
49
Issue
5
Year of publication
1994
Pages
243 - 248
Database
ISI
SICI code
0020-0190(1994)49:5<243:ADVOSA>2.0.ZU;2-T
Abstract
We present direct proofs of the following results of Shamir and Snir [ Mathematical System Theory 13 (1980) 301-322] on the depth of monotone arithmetic circuits over rings of characteristic 0: (1) an OMEGA((log p)(log n)) lower bound for computing the product of p n X n matrices; and (2) an OMEGA(n) lower bound for computing the permanent of an n X n matrix.