Name
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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0020-0190(94)90061-2 | Inf. Process. Lett. |
Keywords | Field | DocType |
monotone circuit depth,direct version,lower bound,parallel algorithms | Binary logarithm,Discrete mathematics,Arithmetic circuits,Combinatorics,Upper and lower bounds,Parallel algorithm,Matrix (mathematics),Mathematical proof,Monotone polygon,Computing the permanent,Mathematics | Journal |
Volume | Issue | ISSN |
49 | 5 | 0020-0190 |
Citations | PageRank | References |
12 | 1.76 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prasoon Tiwari | 1 | 592 | 96.81 |
| Martin Tompa | 2 | 1103 | 149.69 |