A nonlinear lower bound on the practical combinational complexity

DOI10.1007/3-540-55210-3_191zbMath1493.68139OpenAlexW1526667530MaRDI QIDQ5096789

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

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_191

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

• 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
• 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
• 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
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item