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

DOI10.1007/978-3-662-44465-8_2MaRDI QIDQ2922591zbMATH OpenOpenAlexFDO

Authors Nikhil Balaji, Samir Datta, Eric Allender

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_2

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Threshold circuits of small majority-depth
• scientific article; zbMATH DE number 1754588
• scientific article; zbMATH DE number 1351078
• scientific article; zbMATH DE number 512860

Cited in

(11)

• Linear-size constant-depth polylog-threshold circuits
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Dynamic complexity of expansion
• Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• On the Complexity of Value Iteration
• The power word problem
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• The power word problem in graph products
• Root finding with threshold circuits

This page was built for publication: Low-depth uniform threshold circuits and the bit-complexity of straight line programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922591)