ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > AUXILIARY PUSHDOWN AUTOMATA:
Reports tagged with Auxiliary Pushdown Automata:
TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

We investigate the phenomenon of depth-reduction in commutative and non-commutative arithmetic circuits. We prove that in the commutative setting, uniform semi-unbounded arithmetic circuits of logarithmic depth are as powerful as uniform arithmetic circuits of polynomial degree; earlier proofs did not work in the uniform setting. This also provides a unified ... more >>>



ISSN 1433-8092 | Imprint