# Formula complexity of arithmetic multiplication

I'd need some bounds on the size of Boolean formulas (over $$\land$$, $$\lor$$ and $$\neg$$) computing the multiplication of two integers.

I'm not an expert in circuit complexity and I'm crawling through literature. As far as I know, it's known that multiplication is not in $$\mathsf{AC}^0$$, i.e. it cannot be computed by a polynomial-size circuit of constant depth, because it can be used to compute Parity.

But, first of all, what if I relax the restriction on depth? Can it be computed by polynomial-size circuits of, say, logarithmic depth? This would still be a polynomial-size circuit as a whole, right?

Then, this is for circuits, but does this tell me anything on the size of Boolean formulas? At worst, a formula can be exponentially larger than the circuit, but does it happen specifically for any formula for multiplication?

In other words, are there polynomial-size formulas to compute integer multiplication?

Multiplication is well known to be computable in uniform $$\mathrm{TC}^0$$, i.e., by a DLOGTIME-uniform family of constant-depth polynomial-size circuits using (unbounded fan-in) $$\land$$, $$\lor$$, $$\neg$$, and Majority gates. In fact, multiplication is $$\mathrm{TC}^0$$-complete under $$\mathrm{AC}^0$$ Turing reductions.
Consequently, it is also computable in uniform $$\mathrm{NC}^1$$, i.e., by a DLOGTIME-uniform family of bounded fan-in Boolean formulas or circuits of depth $$O(\log n)$$ (thus of polynomial size). Here, uniformity is with respect to the usual infix or prefix representation for formulas, or with respect to the extended connection language for circuits.
Consequently, it is also computable by polynomial-size unbounded fan-in $$\land$$, $$\lor$$, $$\neg$$ circuits of depth $$O(\log n/\log\log n)$$. This is optimal by the usual circuit lower bounds for Parity or Majority.
• Any circuit can be unravelled to a formula of the same depth. Thus bounded fan-in Boolean formulas of depth $O(\log n)$ and bounded fan-in Boolean circuits of depth $O(\log n)$ compute the same class of languages. (This may of course increase the size, but bounded fan-in things of depth $O(\log n)$ have necessaily polynomial size anyway.) Jan 2 at 15:34
• You can look at I. Wegener, The complexity of Boolean functions. The book is rather old (e.g., it predates the definition of TC^0 as a separate class), but it includes the construction of $O(\log n)$ depth multiplication circuits using carry-save addition as well as basic relationships between formula and circuit complexity. Jan 2 at 15:51