All reports by Author Sébastien Tavenas:

__
TR21-094
| 6th July 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### New Non-FPT Lower Bounds for Some Arithmetic Formulas

__
TR21-081
| 14th June 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Revisions: 1

__
TR19-100
| 31st July 2019
__

Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas#### Nonnegative rank measures and monotone algebraic branching programs

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Circuit for a polynomial $P\in F[x_1,\ldots,x_N]$ is a computational model for constructing the polynomial $P$ using only additions and multiplications. It is a \emph{syntactic} model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to ... 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 >>>