A nonlinear lower bound on the practical combinational complexity

DOI10.1016/0304-3975(94)00269-OMaRDI QIDQ673076zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• A nonlinear lower bound on the practical combinational complexity
• scientific article; zbMATH DE number 4102490
• scientific article; zbMATH DE number 4047102
• scientific article; zbMATH DE number 4172392
• 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
• A lower bound on determinantal complexity
• Lower bound for the approximative complexity
• scientific article; zbMATH DE number 139642

Cites work

• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3873237 (Why is no real title available?)
• scientific article; zbMATH DE number 3906394 (Why is no real title available?)
• scientific article; zbMATH DE number 4051518 (Why is no real title available?)
• scientific article; zbMATH DE number 4108150 (Why is no real title available?)
• scientific article; zbMATH DE number 4112041 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3285250 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• A 3n-lower bound on the network complexity of Boolean functions
• A Boolean function requiring 3n network size
• A Separator Theorem for Planar Graphs
• A class of Boolean functions with linear combinational complexity
• Applications of a Planar Separator Theorem
• Communication complexity
• Explicit constructions of linear-sized superconcentrators
• Lower bounds for synchronous circuits and planar circuits
• Lower bounds on the area complexity of Boolean circuits
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• The advantages of a new approach to defining the communication complexity for VLSI
• The planar realization of Boolean functions
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(5)

• A nonlinear lower bound on the practical combinational complexity
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• scientific article; zbMATH DE number 4104386 (Why is no real title available?)
• scientific article; zbMATH DE number 4047102 (Why is no real title available?)
• scientific article; zbMATH DE number 4102490 (Why is no real title available?)

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)