A nonlinear lower bound on the practical combinational complexity

DOI10.1007/3-540-55210-3_191zbMATH Open1493.68139OpenAlexW1526667530MaRDI QIDQ5096789FDOQ5096789

Authors: Xaver Gubáš, Juraj Hromkovič, 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

Recommendations

• A nonlinear lower bound on the practical combinational complexity
• scientific article; zbMATH DE number 4104386
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• scientific article; zbMATH DE number 139642
• scientific article; zbMATH DE number 4102490

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

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Separator Theorem for Planar Graphs
• Communication complexity
• A Boolean function requiring 3n network size
• Explicit constructions of linear-sized superconcentrators
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• A class of Boolean functions with linear combinational complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Title not available (Why is that?)
• The advantages of a new approach to defining the communication complexity for VLSI

Cited In (6)

• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A nonlinear lower bound on the practical combinational complexity

This page was built for publication: A nonlinear lower bound on the practical combinational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096789)