@inbook {IOPORT.05724124,
    author       = {Jansen, Maurice and Sarma M.N., Jayalal},
    title        = {Balancing bounded treewidth circuits.},
    year         = {2010},
    booktitle    = {Computer science -- theory and applications. 5th international computer science symposium in Russia, CSR 2010, Kazan, Russia, June 16--20, 2010. Proceedings},
    isbn         = {978-3-642-13181-3},
    pages        = {228-239},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-13182-0_21},
    abstract     = {Summary: We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For both arithmetic and Boolean circuits, we show that any circuit of size $n ^{O(1)}$ and treewidth $O(\log ^{i } n)$ can be simulated by a circuit of width $O(\log ^{i + 1} n)$ and size $n ^{c }$, where $c = O(1)$, if $i = 0$, and $c = O(\log \log n)$ 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} \log n)$. From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of [14]. As another application, we derive that constant width arithmetic circuits of size $n ^{O(1)}$ can be balanced to depth $O(\log n)$, 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} \log n)$. This strengthens in the non-uniform setting the known inclusion that $\text{SC}^{0} \subseteq \text{NC}^{1}$. Finally, we apply our construction to show that Reachability and Circuit Value Problem for some treewidth restricted cases can be solved in LogDCFL.},
    identifier   = {05724124},
}