Balancing Bounded Treewidth Circuits

Original · EN

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ᵒ⁽¹⁾ and treewidth O(ⁱ n) can be simulated by a circuit of width O(ⁱ⁺¹ n) and size nᶜ, where c = O(1), if i=0, and c=O(n) otherwise. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size nᵒ⁽¹⁾ and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k² n). 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ᵒ⁽¹⁾ can be balanced to depth O(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ᵒ⁽¹⁾ and treewidth k can be simulated by bounded fan-in formulas of depth O(k² n). This strengthens in the non-uniform setting the known inclusion that SC⁰ NC¹. Finally, we apply our construction to show that reachability for directed graphs of bounded treewidth is in LogDCFL.