Nonlinear lower bounds on the number of processors of circuits with sublinear separators

DOI10.1016/0890-5401(91)90041-YzbMath0747.94025OpenAlexW2118157275MaRDI QIDQ1183605

Juraj Hromkovič

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90041-y

zbMATH Keywords

Boolean functioncommunication complexityunbounded fan-in Boolean circuitgraph separationmagnifiers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

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

Cites Work

• A Boolean function requiring 3n network size
• Communication complexity
• The planar realization of Boolean functions
• The advantages of a new approach to defining the communication complexity for VLSI
• Eigenvalues and expanders
• Lower bounds for synchronous circuits and planar circuits
• A 3n-lower bound on the network complexity of Boolean functions
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• A class of Boolean functions with linear combinational complexity
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nonlinear lower bounds on the number of processors of circuits with sublinear separators