Author name cluster

Guillaume Malod

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

STOC Conference 2014 Conference Paper

Lower bounds for depth 4 formulas computing iterated matrix multiplication

Hervé Fournier
Nutan Limaye
Guillaume Malod
Srikanth Srinivasan 0001

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 × n , IMM n,d , has size n Ω(√ d ) as long as d = n O (1) . This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas. We also study ΣΠ [ O ( d / t )] ΣΠ [ t ] formulas, which are depth 4 formulas with the stated bounds on the fan-ins of the Π gates. A recent depth reduction result of Tavenas (MFCS, 2013) shows that any n -variate degree d = n O (1) polynomial computable by a circuit of size poly( n ) can also be computed by a depth 4 ΣΠ [ O ( d / t )] ΣΠ [ t ] formula of top fan-in n O ( d / t ) . We show that any such formula computing IMM n,d has top fan-in n Ω( d / t ) , proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi (ECCC, 2013) which gives a similar lower bound for an explicit polynomial in VNP.

Details

STOC Conference 2012 Conference Paper

Separating multilinear branching programs and formulas

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 multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n -variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size n Ω(log n) .

Details

TCS Journal 2008 Journal Article

Universal relations and #P-completeness

Hervé Fournier
Guillaume Malod

This paper follows the methodology introduced by Agrawal and Biswas in [Manindra Agrawal, Somenath Biswas, Universal relations, in: Structure in Complexity Theory Conference, 1992, pp. 207–220], based on a notion of universality for the relations associated with NP-complete problems. The purpose was to study NP-complete problems by examining the effects of reductions on the solution sets of the associated witnessing relations. This provided a useful criterion for NP-completeness while suggesting structural similarities between natural NP-complete problems. We extend these ideas to the class #P. The notion we find also yields a practical criterion for #P-completeness, as illustrated by a varied set of examples, and strengthens the argument for structural homogeneity of natural complete problems.

Details DOI

MFCS Conference 2006 Conference Paper

Characterizing Valiant's Algebraic Complexity Classes

Guillaume Malod
Natacha Portier

Abstract Valiant introduced 20 years ago a theory to study the complexity of polynomial families. Using arithmetic circuits as computation model, these classes are easy to define and open to combinatorial techniques. In this paper we gather old and new results under a unifying theme, namely the restrictions imposed upon the gates, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and VNP e or the completeness of the determinant for VQP, and new results such as a characterization of the class VP or answers to both a conjecture and a problem raised by Bürgisser [1]. We also show that for circuits of polynomial depth and unbounded size these models have the same expressive power and characterize a uniform version of VNP.

Details