Balancing Bounded Treewidth Circuits

DOI10.1007/978-3-642-13182-0_21zbMATH Open1285.68066arXiv0910.1427OpenAlexW1987462672MaRDI QIDQ3569746FDOQ3569746

Jayalal Sarma M. N., Maurice Jansen

Publication date: 22 June 2010

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: Algorithmic tools for graphs of small treewidth are used to address questions in complexity theory. For both arithmetic and Boolean circuits, it is shown that any circuit of size $n^{O(1)}$ and treewidth $O(lo{g}^{i}n)$ can be simulated by a circuit of width $O(lo{g}^{i+1}n)$ and size $n^c$, where $c=O(1)$, if $i=0$, and $c=O(loglogn)$ otherwise. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size $n^{O(1)}$ and treewidth $k$ can be simulated by bounded fan-in arithmetic formulas of depth $O(k^{2}logn)$. From this we derive the analogous statement for syntactically multilinear arithmetic circuits, which strengthens a theorem of Mahajan and Rao. As another application, we derive that constant width arithmetic circuits of size $n^{O(1)}$ can be balanced to depth $O(logn)$, provided certain restrictions are made on the use of iterated multiplication. Also from our main construction, we derive that Boolean bounded fan-in circuits of size $n^{O(1)}$ and treewidth $k$ can be simulated by bounded fan-in formulas of depth $O(k^{2}logn)$. This strengthens in the non-uniform setting the known inclusion that $S{C}^{0}subseteqN{C}^1$. Finally, we apply our construction to show that {sc reachability} for directed graphs of bounded treewidth is in $LogDCFL$.

Full work available at URL: https://arxiv.org/abs/0910.1427

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (4)

• Small space analogues of Valiant's classes and the limitations of skew formulas
• Balancing bounded treewidth circuits
• A generalization of Spira's theorem and circuits with small segregators or separators
• A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators

   Recommendations

• Balancing bounded treewidth circuits 👍 👎
• On balanced versus unbalanced computation trees 👍 👎
• Bounded Tree-Width and CSP-Related Problems 👍 👎
• Treewidth of graphs with balanced separations 👍 👎
• Spanning Balanced Trees in Boolean Cubes 👍 👎
• A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees 👍 👎
• On balanced separators, treewidth, and cycle rank 👍 👎
• Tight bounds on the algebraic connectivity of a balanced binary tree 👍 👎
• On Tree Circuits 👍 👎

This page was built for publication: Balancing Bounded Treewidth Circuits

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