Balancing bounded treewidth circuits
From MaRDI portal
Publication:1678757
DOI10.1007/s00224-013-9519-3zbMath1380.68315OpenAlexW2571401227MaRDI QIDQ1678757
Maurice Jansen, M. N. Jayalal Sarma
Publication date: 7 November 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9519-3
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ On treewidth, separators and Yao's garbling ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Upper bounds for monotone planar circuit value and variants
- Space-bounded reducibility among combinatorial problems
- Maze recognizing automata and nondeterministic tape complexity
- Characterizing Valiant's algebraic complexity classes
- Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
- Fast Parallel Computation of Polynomials Using Few Processors
- Small-Space Analogues of Valiant’s Classes
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- Undirected ST-connectivity in log-space
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- On Lower Bounds for Constant Width Arithmetic Circuits
- The Parallel Evaluation of General Arithmetic Expressions
- Reachability Problems: An Update
- NC-algorithms for graphs with small treewidth
This page was built for publication: Balancing bounded treewidth circuits
