All reports by Author Suryajith Chillara:

__
TR18-062
| 7th April 2018
__

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

__
TR17-156
| 15th October 2017
__

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan#### Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

__
TR16-096
| 14th June 2016
__

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>