A generalization of Spira's theorem and circuits with small segregators or separators

DOI10.1016/j.ic.2016.09.008zbMath1353.68083OpenAlexW2529464583MaRDI QIDQ342721

Anna Gál, Jing-Tang Jang

Publication date: 18 November 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.09.008

zbMATH Keywords

Boolean circuitsspace complexitycircuit depthcircuit sizeSpira's theorem

Mathematics Subject Classification ID

Related Items (1)

On treewidth, separators and Yao's garbling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds for monotone planar circuit value and variants
• Speedups of deterministic machines by synchronous parallel machines
• Complexity theory of parallel time and hardware
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Circuit size is nonlinear in depth
• Size-depth tradeoffs for Boolean formulae
• Relating monotone formula size and monotone depth of Boolean functions
• Parametrized complexity theory.
• Relationships between nondeterministic and deterministic tape complexities
• A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators
• Fast Parallel Computation of Polynomials Using Few Processors
• A separator theorem for graphs of bounded genus
• The Size and Depth of Layered Boolean Circuits
• Balancing Bounded Treewidth Circuits
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• An Optimal Parallel Algorithm for Formula Evaluation
• On Relating Time and Space to Size and Depth
• Log Space Recognition and Translation of Parenthesis Languages
• The Parallel Evaluation of General Arithmetic Expressions
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Size-Depth Tradeoffs for Algebraic Formulas
• An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
• One-Input-Face MPCVP Is Hard for L, But in LogDCFL

This page was built for publication: A generalization of Spira's theorem and circuits with small segregators or separators