All reports by Author Guillaume Malod:

__
TR16-094
| 6th June 2016
__

Guillaume Lagarde, Guillaume Malod#### Non-commutative computations: lower bounds and polynomial identity testing

Comments: 1

__
TR15-022
| 9th February 2015
__

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for non-commutative skew circuits

Revisions: 1

__
TR14-163
| 29th November 2014
__

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh#### Homomorphism polynomials complete for VP

__
TR13-100
| 15th July 2013
__

HervĂ© Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for depth $4$ formulas computing iterated matrix multiplication

__
TR11-134
| 9th October 2011
__

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff#### Separating multilinear branching programs and formulas

Guillaume Lagarde, Guillaume Malod

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-

alize algebraic branching programs (ABP). This model is called unambiguous because it captures the

polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-

morphic).

We ...
more >>>

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

HervĂ© Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth $4$ arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, IMM$_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>>

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>