Lower Bounds for Tractable Arithmetic Circuits
summary
Shows a concrete lower bound method: define a value matrix rank for any vtree‑induced balanced partition and prove that its rank lower bounds the number of gates in any structured‑decomposable arithmetic circuit, so rank can be exponential in n. Gives an explicit hard family using an expander graph construction (product over edges of 1+x_i x_j) and a proof that one of two factors must be exponentially large because merging two vtree‑aligned circuits takes quadratic time, then uses a fresh variable y to build a small decomposable circuit that forces exponential size for any structured version, establishing a structured‑decomposability vs decomposability separation that holds even with negative weights.
AI-written summary · about