Vince Grolmusz

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 >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

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 >>>

Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

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 >>>