An n logn Lower Bound on Synchronous Combinational Complexity

DOI10.2307/2041447zbMath0402.94041OpenAlexW4241509482MaRDI QIDQ4187739

Lawrence H. Harper

Publication date: 1977

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2041447

zbMATH Keywords

Boolean FunctionsLower Bound on Synchronous Combinational ComplexityNetwork Complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

Lower bounds for synchronous circuits and planar circuits ⋮ Sublinear-communication secure multiparty computation does not require FHE ⋮ The size and depth of layered Boolean circuits

This page was built for publication: An n logn Lower Bound on Synchronous Combinational Complexity