Elementary symmetric polynomials S_n^k are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that S_n^k modulo composite numbers m=p_1p_2
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials x_{i_1}x_{i_2}\cdots x_{i_k} ... more >>>

Let r \geq 1 be an integer. Let us call a polynomial f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}] as a multi-r-ic polynomial if the degree of f with respect to any variable is at most r (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove ... more >>>