Name
Abstract | ||
|---|---|---|
For every k 1, we give an explicit polynomial that is computable by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit of width k. As a consequence we show that the constant-width and the constant-depth hierarchies of monotone arithmetic circuits (both commutative and noncommutative) are infinite. We also prove hardness-randomness tradeoffs for identity testing of constant-width circuits analogous to [6,4]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-10631-6_65 | international symposium on algorithms and computation |
Keywords | DocType | Volume |
computational complexity,lower bound | Journal | abs/0907.3780 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.41 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Pushkar S. Joglekar | 2 | 35 | 5.69 |
| Srikanth Srinivasan | 3 | 132 | 21.31 |