Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ELEMENTARY SYMMETRIC POLYNOMIALS:
Reports tagged with elementary symmetric polynomials:
TR02-052 | 3rd September 2002
Vince Grolmusz

#### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

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

TR15-181 | 13th November 2015
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

#### On the size of homogeneous and of depth four formulas with low individual degree

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

TR19-100 | 31st July 2019
Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

#### Nonnegative rank measures and monotone algebraic branching programs

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

ISSN 1433-8092 | Imprint