Lower bounds on the area complexity of Boolean circuits

DOI10.1016/0304-3975(92)90079-UMaRDI QIDQ1193877zbMATH OpenWikidataFDO

Authors S. A. Lozhkin, Andrej I. Rybko, Nadežda A. Škalikova, Juraj Hromkovič, Alexander Sapozhenko

Publication date 27 September 1992

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

zbMATH Keywords

lower boundBoolean circuitsBoolean functionscommunication complexitylayoutarea complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds for Boolean circuits of bounded negation width
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• Lower bounds for unrestricted Boolean circuits: open problems
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
• Lower bounds for the complexity of restrictions of Boolean functions
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• scientific article; zbMATH DE number 806749
• Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
• scientific article; zbMATH DE number 806753

Cites work

• scientific article; zbMATH DE number 3644978 (Why is no real title available?)
• 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 3878851 (Why is no real title available?)
• scientific article; zbMATH DE number 3817584 (Why is no real title available?)
• scientific article; zbMATH DE number 3906394 (Why is no real title available?)
• scientific article; zbMATH DE number 3906395 (Why is no real title available?)
• scientific article; zbMATH DE number 4051518 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3205680 (Why is no real title available?)
• A result on k-valent graphs and its application to a graph embedding problem
• Communication complexity
• Linear lower bounds on unbounded fan-in Boolean circuits
• The advantages of a new approach to defining the communication complexity for VLSI
• The planar realization of Boolean functions

Cited in

(16)

• scientific article; zbMATH DE number 3878851 (Why is no real title available?)
• scientific article; zbMATH DE number 2032366 (Why is no real title available?)
• Linear lower bounds on unbounded fan-in Boolean circuits
• scientific article; zbMATH DE number 4172915 (Why is no real title available?)
• scientific article; zbMATH DE number 4061152 (Why is no real title available?)
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Asymptotically sharp estimates for the area of multiplexers in the cellular circuit model
• A nonlinear lower bound on the practical combinational complexity
• Lower bounds for synchronous circuits and planar circuits
• scientific article; zbMATH DE number 4045149 (Why is no real title available?)
• scientific article; zbMATH DE number 4104386 (Why is no real title available?)
• Sharp lower bounds involving circuit layout system
• On the complexity of planar Boolean circuits
• scientific article; zbMATH DE number 139639 (Why is no real title available?)
• scientific article; zbMATH DE number 3906394 (Why is no real title available?)
• scientific article; zbMATH DE number 4102490 (Why is no real title available?)

This page was built for publication: Lower bounds on the area complexity of Boolean circuits

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