Lower bounds for synchronous circuits and planar circuits
From MaRDI portal
Publication:1114661
DOI10.1016/0020-0190(89)90172-5zbMath0662.94021MaRDI QIDQ1114661
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
68Q25: Analysis of algorithms and problem complexity
Related Items
Communication Complexity and Lower Bounds on Multilective Computations, A nonlinear lower bound on the practical combinational complexity, A nonlinear lower bound on the practical combinational complexity, Nonlinear lower bounds on the number of processors of circuits with sublinear separators, Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC, On the complexity of planar Boolean circuits
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item