A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators

DOI10.1007/978-3-642-27660-6_22zbMath1298.68090OpenAlexW1492702334MaRDI QIDQ2891374

Jing-Tang Jang, Anna Gál

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_22

Mathematics Subject Classification ID

Related Items (2)

A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds for monotone planar circuit value and variants
• Speedups of deterministic machines by synchronous parallel machines
• Circuit size is nonlinear in depth
• Size-depth tradeoffs for Boolean formulae
• Relating monotone formula size and monotone depth of Boolean functions
• Relationships between nondeterministic and deterministic tape complexities
• 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
• Size-Depth Tradeoffs for Algebraic Formulas
• 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