Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-177 | 28th June 2014 00:21

Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

RSS-Feed




Revision #1
Authors: Eric Allender, Nikhil Balaji, Samir Datta
Accepted on: 28th June 2014 00:21
Downloads: 1038
Keywords: 


Abstract:

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy.



Changes to previous version:

Minor corrections


Paper:

TR13-177 | 10th December 2013 04:36

Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs





TR13-177
Authors: Eric Allender, Nikhil Balaji, Samir Datta
Publication: 10th December 2013 04:37
Downloads: 2095
Keywords: 


Abstract:

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy.



ISSN 1433-8092 | Imprint