Lower Bounds on Synchronous Combinational Complexity

DOI10.1137/0208009MaRDI QIDQ4199522zbMATH OpenOpenAlexFDO

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

Boolean functioncombinational complexitydeterminantlogic circuitsmarriage problemsynchronous circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(4)

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

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)