A nonlinear lower bound on the practical combinational complexity

DOI10.1016/0304-3975(94)00269-OzbMath0873.68063OpenAlexW2083736288MaRDI QIDQ673076

Xaver Gubáš, Juraj Waczulík, Juraj Hromkovič

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00269-o

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• Communication complexity
• The planar realization of Boolean functions
• Lower bounds for synchronous circuits and planar circuits
• A 3n-lower bound on the network complexity of Boolean functions
• Explicit constructions of linear-sized superconcentrators
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• Lower bounds on the area complexity of Boolean circuits
• 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
• The advantages of a new approach to defining the communication complexity for VLSI