TY - GEN

T1 - Low-depth uniform threshold circuits and the bit-complexity of straight line programs

AU - Allender, Eric

AU - Balaji, Nikhil

AU - Datta, Samir

PY - 2014

Y1 - 2014

N2 - 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 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.

AB - 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 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.

UR - http://www.scopus.com/inward/record.url?scp=84906244716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906244716&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44465-8_2

DO - 10.1007/978-3-662-44465-8_2

M3 - Conference contribution

AN - SCOPUS:84906244716

SN - 9783662444641

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings

PB - Springer Verlag

T2 - 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014

Y2 - 25 August 2014 through 29 August 2014

ER -