Search Results

1 of 1
Edit My Search | New Search | Selected Items
thumbnail image
PDF
PDF-1(290.99 kb)
Citation & Export
View statistics
Staff View

Citation & Export
Hide

Simple citation

Allender, Eric & Balaji, Nikhil & Datta, Samir (2014). Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs. Lecture Notes in Computer Science, 8635, 13-24. Retrieved from https://doi.org/doi:10.7282/T3S184BR

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs (2014)
Eric Allender, Nikhil Balaji, Samir Datta
Lecture Notes in Computer Science 8635: 13-24.
Link to published version
VersionAccepted Manuscript (AM)
AbstractWe 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.
Persistent URLhttps://doi.org/doi:10.7282/T3S184BR
SubjectsBitSLP, Counting hierarchy, Division, Matrix powering, Multiplication, Complex, Threshold circuits
RightsCopyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.