scientific article; zbMATH DE number 4003533

MaRDI QIDQ4728251zbMATH OpenFDO

Authors James Lynch

Publication date 1986

zbMATH Keywords

complexity of unbounded fan-in circuitsdepthsizesmall cliquesTuring Machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Depth reduction for circuits of unbounded fan-in
• scientific article; zbMATH DE number 1256716
• Size--Depth Tradeoffs for Threshold Circuits
• Lower bounds for recognizing small cliques on CRCW PRAM's
• Circuits with medium fan-in

Cited in

(8)

• Computing majority by constant depth majority circuits with low fan-in gates
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Depth lower bounds for monotone semi-unbounded fan-in circuits.
• A generalization of Spira's theorem and circuits with small segregators or separators
• scientific article; zbMATH DE number 4068311 (Why is no real title available?)
• Circuit Bottom Fan-in and Computational Power
• Exponential lower bounds for the pigeonhole principle
• Lower bounds for recognizing small cliques on CRCW PRAM's

This page was built for publication:

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