Threshold Circuits for Iterated Matrix Product and Powering

DOI10.1051/ITA:2000105MaRDI QIDQ4494480zbMATH OpenOpenAlexFDO

Authors Carlo Mereghetti, Beatrice Palano

Publication date 13 June 2001

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2000__34_1_39_0/, https://eudml.org/doc/222041

zbMATH Keywords

complexity of computing

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 512860
• On Threshold Circuits and Polynomial Computation
• Threshold circuits of small majority-depth
• Powering requires threshold depth 3
• On Optimal Depth Threshold Circuits for Multiplication and Related Problems

Cites work

• scientific article; zbMATH DE number 1809724 (Why is no real title available?)
• scientific article; zbMATH DE number 4009825 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 773997 (Why is no real title available?)
• scientific article; zbMATH DE number 773998 (Why is no real title available?)
• scientific article; zbMATH DE number 3346572 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
• Regular languages in \(NC\)
• Threshold Circuits for Iterated Matrix Product and Powering
• Very Fast Parallel Polynomial Arithmetic

Cited in

(4)

• scientific article; zbMATH DE number 6292740 (Why is no real title available?)
• Threshold Circuits for Iterated Matrix Product and Powering
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• Few Product Gates But Many Zeros

This page was built for publication: Threshold Circuits for Iterated Matrix Product and Powering

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