Login
Talks & Seminars
Title: A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Dr. Suryajith Chillara, IIT Bombay
Date & Time: August 6, 2018 14:00
Venue: Room no. 109, 01st Floor, Department of Computer Science and Engineering, New CSE/CC Building
Abstract:
An arithmetic circuit is a natural model of computation for polynomials. It implicitly corresponds to the (nested) arithmetic expression of the polynomial computation, of the form \sum\product\sum\product ... \sum\product {for d times}. The size of the circuit corresponds to the total number of arithmetic operations (+, x) involved and the depth of the circuit corresponds to the depth of nesting. If there are at most D nested products in an arithmetic expression, we say that it has a product depth of D. Here we study the blow up of size that is involved in converting an algebraic circuits of product depth D+1 into an algebraic circuit of depth D when every computation is restricted to multilinear polynomial, and show that the blow up in size is “exponential”. In particular, we show that for every D \leq o(log n/log log n), there is a polynomial P_D on n variables that can be computed by a multilinear formula of depth D+1 and size O(n) but cannot be computed by any multilinear formula of depth D and size exp(n^{1/D}). This strengthens the result of Raz and Yehudayoff (Computational Complexity 2009) who showed a quasipolynomial separation, and the result of Kayal, Nair and Saha (STACS 2016) who gave an exponential separation when D=1. (Joint work with Christian Engels (CSE, IITB), Nutan Limaye (CSE, IITB) and Srikanth Srinivasan (Math, IITB))
Speaker Profile:
Suryajith Chillara is a Post Doc Fellow in the Dept. of CSE, IIT Bombay. More details about him are available at https://www.cse.iitb.ac.in/~suryajith/.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback