|
3.30 pm,Seminar Hall Complexity of Computing Polynomials of Bounded Individual Degree Suryajith Chillara IIT Bombay. 09-09-19 Abstract In this talk, we are interested in computing polynomials symbolically. That is, given variables {x_1, x_2, …, x_n} and some constants {a_1, a_2, …}, we are interested in finding out how many arithmetic operations {+,x} are needed to compute a target polynomial f(x_1, x_2, …, x_n). For example, a computation of the form (1+x_1)(1+x_2)…(1+x_n) has n additions and one multiplication (with unbounded operands). This is a succinct expression for computing a polynomial with 2^n many monomials. This notion of computation of polynomials and its complexity can be formalized in terms of arithmetic circuits as follows. Arithmetic circuits are Directed Acyclic Graphs (DAGs) whose input nodes are labelled either by variables or constants and every other node is labelled by + or x. The flow of computation flows from the leaves to root as follows: The polynomial computed at the input nodes is the label itself. The polynomial computed at every other node is obtained by operating upon the polynomials computed at its predecessors and this operation is defined by the node's label. Number of nodes in the arithmetic circuit corresponds to the number of arithmetic operations required to compute a polynomial. Thus, the size of the arithmetic circuit is the right notion of complexity in this computational model. Given a computational model, it is natural to ask what the “easy” tasks are and what the “hard” tasks are. Formally, Upper Bounds: for what class of polynomials on n variables do we need super-polynomially (in n) many operations to compute them? Similarly, Lower Bounds: for what class of polynomials on n variables do we just need polynomially (in n) many operations to compute them? It was well known that computing the Determinant of an n x n symbolic matrix is “easy”. Valiant conjectured that computing the Permanent of an n x n symbolic matrix is “hard”. Towards this, the goal is to show that computation of Permanent of a n x n matrix needs arithmetic circuits of super-polynomial size. However, the best known lower bounds are sub-quadratic. To tackle this hindrance, researchers have looked at some natural restrictions on arithmetic circuits, with a hope that progress here would throw light on the general model. In this talk we look at Bounded Individual Degree restriction. That is, the polynomial computed at every node in the circuit is a polynomial of bounded individual degree. If bound on the individual degree is 1, then the polynomial computed every node is a multilinear polynomial. In this restricted setting, researchers have been able to prove strong lower bounds. In this talk, I shall briefly survey the progress made in proving lower bounds for multilinear circuits and multi-k-ic circuits (circuits of bounded individual degree k). I shall then present some new lower bounds in this setting, based on my work with Christian Engels, Nutan Limaye and Srikanth Srinivasan. Talk assumes no prior knowledge of the subject.
|
