Abstract:

We expand the lower bound frontier in arithmetical circuit complexity for several recently considered restricted computational models. The main results are the following.

First, Shpilka and Wigderson's partial derivative method for sigma-pi-sigma formulas is refined to include additive complexity in the lower bound. Consequently, we strengthen some lower bounds on total sigma-pi-sigma formula size. A supplementary method is derived, that is shown to yield quadratic lower bounds for polynomials for which the partial derivatives method fails.

Second, we continue the recent study of bilinear circuits with bounded coefficients. Generic lower bounds are proved for bilinear maps that are in the orbit of the circular convolution mapping. This leads to a study of universal-existential quantified predicates about minors of the discrete Fourier matrix. We prove a quantative lower bound on the expected value of the determinant of certain random Vandermonde matrices with nodes on the unit circle in the complex plane. This result is used to establish circuit lower bounds.

Finally, bounded depth circuits are investigated. We prove a nonlinear lower bound for circular convolution in case the input length is prime. The proof uses a superconcentrator lemma by Raz and Shpilka and the discrete uncertainty principle for cyclic groups of prime order by Tao.