Lower Bounds on Synchronous Combinational Complexity

DOI10.1137/0208009zbMATH Open0412.68037OpenAlexW2074419571MaRDI QIDQ4199522FDOQ4199522

Authors: Lawrence H. Harper, John Savage 

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0208009

zbMATH Keywords

determinantBoolean functionmarriage problemlogic circuitscombinational complexitysynchronous circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (4)

• Lower bounds for synchronous circuits and planar circuits
• Constructive universal algebra: An introduction
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
• The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms

This page was built for publication: Lower Bounds on Synchronous Combinational Complexity

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