A nonlinear lower bound on the practical combinational complexity
DOI10.1016/0304-3975(94)00269-OzbMATH Open0873.68063OpenAlexW2083736288MaRDI QIDQ673076FDOQ673076
Authors: Xaver Gubáš, Juraj Hromkovič, Juraj Waczulík 
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
Recommendations
- A nonlinear lower bound on the practical combinational complexity
- scientific article
- scientific article; zbMATH DE number 4047102
- scientific article
- scientific article; zbMATH DE number 3934407
- Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
- A lower bound on determinantal complexity
- scientific article; zbMATH DE number 7711586
- Lower bound for the approximative complexity
- scientific article
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
- Applications of a Planar Separator Theorem
- 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?)
- 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
- Lower bounds on the area complexity of Boolean circuits
- 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?)
- Title not available (Why is that?)
- The advantages of a new approach to defining the communication complexity for VLSI
Cited In (4)
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 Q673076)
