Talks & Seminars
Title: A Quadratic Size-Hierarchy Theorem For Small-Depth Multilinear Formulas
Dr. Suryajith Chillara, Dept. of CSE, IIT Bombay
Date & Time: July 4, 2018 12:05
Venue: Room no. 109, 01st Floor, Department of Computer Science and Engineering, New CSE/CC Building
Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial. It is an important question in the study of algebraic computational complexity to understand the amount of computational resources (refers to size of the formulas in this case) needed to compute a given polynomial. In this talk, we will restrict ourselves to arithmetic formulas where computation at every vertex is a multilinear polynomial and in this scenario we show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. The multilinear restriction is a reasonable one since most polynomials of interest are indeed multilinear, Determinant, Permanent, Iterated Matrix Multiplication, Elementary Symmetric Polynomial. etc. Formally, we will show that for any s = poly(n) and \delta > 0, we show that there are explicit polynomial families that have multilinear formulas of size at most s but no 'small'-depth multilinear formulas of size less than s^{0.5 - \delta}. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using \epsilon-biased spaces. (Joint work with Nutan Limaye and Srikanth Srinivasan)
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback