Survey of some recent results in algebraic complexity

Algebraic complexity studies the complexity of computing polynomials by arithmetic circuits - i.e. circuits that use the arithmetic operations +,*. Arithmetic circuits form a very elegant model of computation in which the (analogue of the) P vs. NP problem may be easier to attack. In recent years algebraic complexity has gained a lot of interest and some breakthrough results were obtained. In this talk, we will mention those breakthrough results and discuss some of the recent developments. In particular, we will mention results regarding depth reduction, lower bounds and algorithms for polynomial identity testing. Speaker: Amir Shpilka, Tel Aviv University. Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab... Faculty of Computer Science: https://cs.hse.ru/en/ Follow us:   / hsefcs  ,   / cs_hse