Sign in
Back
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
Accepted manuscript   Open access   Peer reviewed

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

Eric Allender, Nikhil Balaji and Samir Datta
Lecture Notes in Computer Science, Vol.8635, pp.13-24
MFCS 2014 (Budapest, Hungary, 2014)
2014
DOI:
https://doi.org/10.7282/T3S184BR

Abstract

BitSLP Counting hierarchy Division Matrix powering Multiplication, Complex Threshold circuits
We present improved uniform TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (as 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.
pdf
skeleton187.24 kBDownloadView
Accepted Manuscript Open Access
url
http://dx.doi.org/10.1007/978-3-662-44465-8_2View
Lecture Notes in Computer Science
url
https://dx.doi.org/10.1007/978-3-662-44465-8View

Metrics

371 File downloads
118 Record Views

Details