Tata Institute of Fundamental Research

An Exponential Depth-Hierarchy Theorem for Constant-Depth Multilinear Circuits

STCS Colloquium
Speaker: Srikanth Srinivasan (Indian Institute of Technology Department of Mathmetics Powai Mumbai 400076)
Organiser: Piyush Srivastava
Date: Tuesday, 5 Dec 2017, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  We study the size blow-up that is necessary to convert an algebraic circuit of constant product-depth D+1 to one of product-depth D in the multilinear setting.
We show that for every constant $D \geq 1$, there is an explicit multilinear polynomial $P_D$ on $n$ variables that can be computed by a multilinear formula of product-depth $D+1$ and size $n$, but not by any multilinear circuit of product-depth $D$ and size less than $\exp(n^{a_D})$ where $a_D$ is some constant that depends on $D$.
This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who proved a quasipolynomial separation, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case$ D=1$.
I will outline the basic ideas behind the proof of this result
Joint work with Suryajith Chillara (CSE IITB), Christian Engels (CSE IITB) and Nutan Limaye (CSE IITB).