A generalization of Spira's theorem and circuits with small segregators or separators
From MaRDI portal
Publication:342721
DOI10.1016/j.ic.2016.09.008zbMath1353.68083OpenAlexW2529464583MaRDI QIDQ342721
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
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
