3 papers
cs.CC2021
Functional lower bounds for restricted arithmetic circuits of depth four
Suryajith Chillara
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit -variate and degree polynomial such that if any depth four cir…
cs.CC2018
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye +1
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth to one of product-depth in the multilinear setting. We show that for every po…
cs.CC2017
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
In this paper, we study the algebraic formula complexity of multiplying many matrices, denoted , and show that the well-known divide-and-conquer a…