On the depth complexity of the counting functions

DOI10.1016/0020-0190(90)90036-WMaRDI QIDQ912617zbMATH OpenOpenAlexFDO

Authors Andrew Chin

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90036-w

zbMATH Keywords

Boolean functionparallel algorithmscommunication complexitycircuit depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Recommendations

• Upper bounds for the size and the depth of formulae for MOD-functions
• Upper bounds on the depth of symmetric Boolean functions
• Communication complexity towards lower bounds on circuit depth
• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• Lower bounds for modular counting by circuits with modular gates

Cites work

• scientific article; zbMATH DE number 3619806 (Why is no real title available?)
• $\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas
• A note on the formula size of the ``mod k functions
• Shallow circuits and concise formulae for multiple addition and multiplication

Cited in

(6)

• New bounds on the half-duplex communication complexity
• scientific article; zbMATH DE number 549850 (Why is no real title available?)
• Upper bounds for the size and the depth of formulae for MOD-functions
• Communication complexity towards lower bounds on circuit depth
• On Combinatorial Depth Measures
• Computing and Verifying Depth Orders

This page was built for publication: On the depth complexity of the counting functions

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