On the depth complexity of the counting functions

DOI10.1016/0020-0190(90)90036-WzbMath0698.68041OpenAlexW2089182858MaRDI QIDQ912617

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

parallel algorithmsBoolean functioncommunication complexitycircuit depth

Mathematics Subject Classification ID

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

Related Items (2)

New bounds on the half-duplex communication complexity ⋮ Upper bounds for the size and the depth of formulae for MOD-functions

Cites Work

• Unnamed Item
• A note on the formula size of the ``mod k functions
• Shallow circuits and concise formulae for multiple addition and multiplication
• $\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas

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