Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ITERATED MATRIX MULTIPLICATION:
Reports tagged with Iterated Matrix Multiplication:
TR11-083 | 22nd May 2011
Eric Allender, Fengming Wang

#### On the power of algebraic branching programs of width two

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several
settings.

more >>>

TR13-028 | 14th February 2013
Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

#### Arithmetic Circuit Lower Bounds via MaxRank

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove
super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

TR15-154 | 22nd September 2015
Neeraj Kayal, Vineet Nair, Chandan Saha

#### Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

TR15-181 | 13th November 2015
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

#### On the size of homogeneous and of depth four formulas with low individual degree

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

TR17-021 | 11th February 2017
Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

#### Reconstruction of full rank Algebraic Branching Programs

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

TR17-034 | 21st February 2017
Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

#### On algebraic branching programs of small width

Revisions: 1

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

ISSN 1433-8092 | Imprint