Sign in
Back
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
Book chapter   Peer reviewed

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

Eric Allender, Nikhil Balaji and Samir Datta
Mathematical Foundations of Computer Science 2014, pp.13-24
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2014
DOI: https://doi.org/10.1007/978-3-662-44465-8_2

Abstract

Binary Expansion Arithmetic Circuit Polynomial Size Matrix Power Discrete Fourier Transform
We present improved uniform TC0 circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (as studied by Maciel and Thérien). 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.

Metrics

6 Record Views

Details