Paper Info
Title
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.
Abstract
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 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.
Year
DOI
Venue
2013
10.1007/978-3-662-44465-8_2
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8635
0302-9743
Citations 
PageRank 
References 
4
0.41
19
Authors
3
Name
Order
Citations
PageRank
Eric Allender11434121.38
Nikhil Balaji294.24
Samir Datta320019.82