An n logn Lower Bound on Synchronous Combinational Complexity

DOI10.2307/2041447MaRDI QIDQ4187739zbMATH OpenOpenAlexFDO

Authors 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)

Cited in

(3)

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

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

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