Lower bounds for synchronous circuits and planar circuits

DOI10.1016/0020-0190(89)90172-5zbMath0662.94021OpenAlexW2072885355MaRDI QIDQ1114661

György Turán

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90172-5

zbMATH Keywords

one-output Boolean functionsplanar circuit complexitysynchronous circuit complexity

Mathematics Subject Classification ID

Related Items (6)

Communication Complexity and Lower Bounds on Multilective Computations ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ On the complexity of planar Boolean circuits ⋮ Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit constructions of linear-sized superconcentrators
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Universal circuits (Preliminary Report)
• An n logn Lower Bound on Synchronous Combinational Complexity
• Lower Bounds on Synchronous Combinational Complexity

This page was built for publication: Lower bounds for synchronous circuits and planar circuits