Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-073 | 6th September 2009 14:29

On Lower Bounds for Constant Width Arithmetic Circuits

RSS-Feed




TR09-073
Authors: Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan
Publication: 6th September 2009 19:28
Downloads: 1584
Keywords: 


Abstract:

The 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].



ISSN 1433-8092 | Imprint