| Title | : | Affine projections of polynomials - A Walk through Algebraic Complexity Theory and beyond |
| Speaker | : | Ramya C (IITM) |
| Details | : | Tue, 12 Apr, 2016 3:00 PM @ BSB 361 |
| Abstract: | : | Polynomials are the most fundamental objects in algebra. It is natural to ask how to compute polynomials efficiently?
That is, given a polynomial we want to understand the number of arithmetic operations needed to compute it. Leslie G. Valiant introduced the notion of arithmetic circuits as a model for computing polynomials and defined algebraic analogues of P and NP - polynomials that are efficiently computable(class VP) and those not known to be efficiently computable(class VNP). While there is a polynomial time algorithm for computing the ``determinant'' of a matrix, the ``permanent'' (viewed as a polynomial) is not known to be easily computable. In fact, Valiant showed that permanent is VNP-complete and conjectured that permanent is not computable by polynomial number of arithmetic operations. Subsequent to Valiant's conjecture, proving lower bounds for circuits computing permanent have been of much interest. While the answer to Valiant's conjecture seems to be at a distance, we look at projections of polynomials. More specifically, affine projections of polynomials. If a polynomial f can be obtained by replacing each variable in a polynomial g by an affine combination of the variables in f then f is said to be an affine projection of g. It is known that the resolving Valiant's conjecture is equivalent to showing that it is hard to represent permanent as a projection of determinant. In this talk we will view models of arithmetic circuits from the perspective of projections of polynomials. We look at circuits built over affine projections of polynomials and look to prove exponential lower bounds for those circuits models. We propose to prove exponential lower bounds for circuits built over affine projections of specific polynomials such as Vandermonde polynomials, Read-Once polynomials etc. |
