Threshold Circuits for Iterated Matrix Product and Powering

DOI10.1051/ITA:2000105zbMATH Open0962.68089OpenAlexW2123814675MaRDI QIDQ4494480FDOQ4494480

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/

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

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)

Cites Work

• A taxonomy of problems with fast parallel algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regular languages in \(NC\)
• Very Fast Parallel Polynomial Arithmetic
• Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold Circuits for Iterated Matrix Product and Powering

Cited In (4)

• Title not available (Why is that?)
• 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)