All reports by Author Sébastien Tavenas:

__
TR23-191
| 2nd December 2023
__

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Power of Homogeneous Algebraic Formulas

__
TR23-009
| 14th February 2023
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas#### Towards Optimal Depth-Reductions for Algebraic Formulas

__
TR22-090
| 24th June 2022
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

__
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

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

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