ECCC-Report TR09-073https://eccc.weizmann.ac.il/report/2009/073Comments and Revisions published for TR09-073en-usSun, 06 Sep 2009 19:28:10 +0300
Paper TR09-073
| On Lower Bounds for Constant Width Arithmetic Circuits |
Vikraman Arvind,
Pushkar Joglekar,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2009/073The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.
1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit of width k. It follows, from the definition of the polynomial, that the constant-width and the constant-depth hierarchies of monotone arithmetic circuits are infinite, both in the commutative and the noncommutative settings.
2. We prove hardness-randomness tradeoffs for identity testing constant-width commutative circuits analogous to [KI03,DSY08].
Sun, 06 Sep 2009 19:28:10 +0300https://eccc.weizmann.ac.il/report/2009/073