On the complexity of planar Boolean circuits

DOI10.1007/BF01277954MaRDI QIDQ1842774zbMATH OpenOpenAlexFDO

Authors Gy. Turán

Publication date 19 July 1995

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01277954

zbMATH Keywords

planar graphscircuit complexityplanar circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Lower bounds for synchronous circuits and planar circuits
• scientific article; zbMATH DE number 4104386
• On the planar monotone computation of Boolean functions
• Lower bounds on the area complexity of Boolean circuits
• scientific article; zbMATH DE number 4172377

Cites work

• scientific article; zbMATH DE number 3858396 (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 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1346515 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• A Separator Theorem for Planar Graphs
• A framework for solving VLSI graph layout problems
• Applications of a Planar Separator Theorem
• Explicit constructions of linear-sized superconcentrators
• Lower bounds for synchronous circuits and planar circuits
• Lower bounds to the complexity of symmetric Boolean functions
• Meanders and their applications in lower bounds arguments
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Multiple cuts, input repetition, and VLSI complexity
• Planar Crossovers
• The performance of multilective VLSI algorithms
• The planar realization of Boolean functions
• Two tapes versus one for off-line Turing machines

Cited in

(13)

• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Succinct certification of monotone circuits
• scientific article; zbMATH DE number 4172377 (Why is no real title available?)
• Planar acyclic computation
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Lower bounds for synchronous circuits and planar circuits
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• Succinct monotone circuit certification: planarity and parameterized complexity
• On Planar Boolean CSP
• Using Flexibility in P-Circuits by Boolean Relations
• Communication Complexity and Lower Bounds on Multilective Computations
• On the planar monotone computation of Boolean functions
• scientific article; zbMATH DE number 3906394 (Why is no real title available?)

This page was built for publication: On the complexity of planar Boolean circuits

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