Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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-
We ... more >>>

TR15-022 | 9th February 2015
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for non-commutative skew circuits

Revisions: 1

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

TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Homomorphism polynomials complete for VP

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

TR13-100 | 15th July 2013
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for depth $4$ formulas computing iterated matrix multiplication

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

TR11-134 | 9th October 2011
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

Separating multilinear branching programs and formulas

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

ISSN 1433-8092 | Imprint